Reinforcement Learning Foundation

Code files

Now that you understand the Bellman Equation, this lecture demonstrates how to use it to solve a Markov Decision Process (MDP) in practice.

You will learn two foundational algorithms:

• Value Iteration
• Policy Iteration

Both algorithms aim to find the optimal policy (π*), meaning the best possible strategy for making decisions. Although they ultimately converge to the same solution, they follow different approaches to get there.

Throughout the lecture, both methods are explained step by step using simple examples, including a 3-state corridorand a 3×3 grid environment, making it easier to understand how each algorithm works and how they compare.

الآن بعد أن أصبحت تفهم معادلة بيلمان (Bellman Equation)، توضح هذه المحاضرة كيفية استخدامها لحل عملية اتخاذ القرار الماركوفي (MDP) بشكل عملي.

ستتعلم خوارزميتين أساسيتين:

• Value Iteration (تكرار القيم)
• Policy Iteration (تكرار السياسات)

تهدف كلتا الخوارزميتين إلى الوصول إلى السياسة المثالية (π*)، أي أفضل استراتيجية ممكنة لاتخاذ القرارات. وعلى الرغم من أن كلتا الطريقتين تصلان إلى نفس الحل الأمثل، إلا أنهما تتبعان أساليب مختلفة للوصول إليه.

خلال المحاضرة، سيتم شرح كل خوارزمية خطوة بخطوة باستخدام أمثلة بسيطة، مثل ممر مكون من 3 حالات وشبكة 3×3، مما يساعد على فهم كيفية عمل كل طريقة ومقارنة الاختلافات بينهما.

Now that you understand the Bellman Equation, this lecture demonstrates how to use it to solve a Markov Decision Process (MDP) in practice.

You will learn two foundational algorithms:

• Value Iteration
• Policy Iteration

Both algorithms aim to find the optimal policy (π*), meaning the best possible strategy for making decisions. Although they ultimately converge to the same solution, they follow different approaches to get there.

Throughout the lecture, both methods are explained step by step using simple examples, including a 3-state corridorand a 3×3 grid environment, making it easier to understand how each algorithm works and how they compare.

الآن بعد أن أصبحت تفهم معادلة بيلمان (Bellman Equation)، توضح هذه المحاضرة كيفية استخدامها لحل عملية اتخاذ القرار الماركوفي (MDP) بشكل عملي.

ستتعلم خوارزميتين أساسيتين:

• Value Iteration (تكرار القيم)
• Policy Iteration (تكرار السياسات)

تهدف كلتا الخوارزميتين إلى الوصول إلى السياسة المثالية (π*)، أي أفضل استراتيجية ممكنة لاتخاذ القرارات. وعلى الرغم من أن كلتا الطريقتين تصلان إلى نفس الحل الأمثل، إلا أنهما تتبعان أساليب مختلفة للوصول إليه.

خلال المحاضرة، سيتم شرح كل خوارزمية خطوة بخطوة باستخدام أمثلة بسيطة، مثل ممر مكون من 3 حالات وشبكة 3×3، مما يساعد على فهم كيفية عمل كل طريقة ومقارنة الاختلافات بينهما.

Dynamic Programming (DP) is mathematically elegant and powerful — but it also has important practical limitations.

In this lecture, we take an honest look at where DP works well, where it fails, and why its limitations led to the development of more advanced RL algorithms.

You will learn why DP performs effectively in small, fully known environments, but struggles with large or unknown problems. Most importantly, this lecture explains how the algorithms covered in the rest of the course were designed to overcome one or more of these limitations.

تُعد البرمجة الديناميكية (Dynamic Programming - DP) من أكثر الأساليب أناقةً وقوةً من الناحية الرياضية، لكنها في الوقت نفسه تمتلك قيودًا عملية مهمة.

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

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

This lecture introduces the motivation behind the entire section by explaining where Dynamic Programming (DP) fails in real-world problems.

Students will learn why environments such as Blackjack, Atari games, and robotics make DP impractical or impossible to apply due to unknown dynamics, large state spaces, or continuous environments.

The lecture then introduces Monte Carlo (MC) methods as a solution. Instead of relying on a complete model of the environment, MC methods learn directly from real experience and sampled episodes.

The lecture concludes with the key idea behind Monte Carlo learning:

“Play many episodes, observe the outcomes, and average the returns.”

توضح هذه المحاضرة الدافع الأساسي لهذا القسم بالكامل من خلال شرح الأسباب التي تجعل البرمجة الديناميكية (DP) غير مناسبة في العديد من مشكلات العالم الحقيقي.

سيتعلم الطلاب لماذا تصبح بيئات مثل Blackjack، وألعاب Atari، والروبوتات صعبة أو مستحيلة التطبيق باستخدام DP، بسبب عدم معرفة البيئة بالكامل، أو ضخامة مساحة الحالات، أو وجود حالات وأفعال مستمرة.

بعد ذلك، تقدم المحاضرة طرق مونت كارلو (Monte Carlo - MC) كحل عملي لهذه المشكلة. فبدلًا من الاعتماد على نموذج كامل للبيئة، تعتمد MC على التعلم من التجارب الفعلية والحلقات (Episodes) التي يتم ملاحظتها.

وتختتم المحاضرة بالفكرة الأساسية لتعلم مونت كارلو:

“قم بتجربة عدد كبير من الحلقات، راقب النتائج، ثم احسب متوسط العوائد التي تحصل عليها.”

Now that the motivation behind Monte Carlo (MC) methods is clear, this lecture introduces the actual MC prediction algorithm used to estimate state values.

Students will learn:

• The incremental update rule, used to improve value estimates over time.
• The difference between First-Visit MC and Every-Visit MC methods.
• How value estimates emerge by walking through a complete episode step by step.

The lecture explains that both approaches eventually converge to the same true state-value function V(s). The main difference lies in which method is easier to prove mathematically and which is simpler to implement in code.

الآن بعد أن أصبحت الدوافع وراء طرق مونت كارلو (Monte Carlo - MC) واضحة، تشرح هذه المحاضرة خوارزمية التنبؤ (Prediction Algorithm) الفعلية المستخدمة لتقدير قيم الحالات.

سيتعلم الطلاب:

• قاعدة التحديث التدريجي (Incremental Update Rule) المستخدمة لتحسين تقديرات القيم مع الوقت.
• الفرق بين First-Visit MC و Every-Visit MC.
• كيفية ظهور تقديرات القيم من خلال تتبع حلقة كاملة (Episode) خطوة بخطوة.

توضح المحاضرة أن كلا الطريقتين تصلان في النهاية إلى دالة قيمة الحالة الحقيقية V(s). ويكمن الاختلاف الأساسي في أي الطريقتين أسهل في الإثبات الرياضي وأيهما أبسط في التنفيذ البرمجي.

Prediction focuses on estimating V(s) for a fixed policy, while Control aims to discover the optimal policy.

This lecture is one of the most important in the section because it walks through a complete Generalized Policy Iteration (GPI) cycle step by step using a simple 3-state corridor example.

Students will learn the three key stages of MC Control:

• Generate → collect experience through episodes
• Evaluate → estimate state values based on returns
• Improve → update the policy to make better decisions

The lecture then introduces ε-greedy exploration, a strategy that balances exploration (trying new actions) and exploitation (choosing the best-known action).

Finally, students are shown the complete Monte Carlo Control algorithm in just a few lines of Python, enabling them to implement an end-to-end MC control solution on their own.

يركز Prediction على تقدير دالة قيمة الحالة V(s) عند اتباع سياسة ثابتة، بينما يهدف Control إلى إيجاد السياسة المثلى (Optimal Policy).

تُعد هذه المحاضرة من أهم المحاضرات في هذا القسم، حيث تشرح دورة كاملة من التكرار العام للسياسات (Generalized Policy Iteration - GPI) خطوة بخطوة باستخدام مثال بسيط لممر مكوّن من 3 حالات.

سيتعلم الطلاب المراحل الأساسية الثلاث في Monte Carlo Control:

• Generate (التوليد) → جمع الخبرات من خلال الحلقات (Episodes)
• Evaluate (التقييم) → تقدير قيم الحالات بناءً على العوائد
• Improve (التحسين) → تحديث السياسة لاتخاذ قرارات أفضل

بعد ذلك، تقدم المحاضرة مفهوم الاستكشاف باستخدام ε-greedy، وهي استراتيجية توازن بين الاستكشاف (تجربة أفعال جديدة)والاستغلال (اختيار أفضل فعل معروف).

وفي النهاية، يتم عرض خوارزمية Monte Carlo Control الكاملة باستخدام عدد قليل من أسطر Python، مما يمكّن الطلاب من بناء وتنفيذ حل متكامل لـ MC Control من البداية إلى النهاية.

On-policy Monte Carlo (MC) uses the same policy for both acting and learning, which can be limiting in many real-world situations.

This lecture introduces two important concepts:

• Behavior Policy (b): the policy used to collect data and interact with the environment.
• Target Policy (π): the policy we actually want to evaluate or learn about.

Students will then learn Importance Sampling, a technique that adjusts or reweights returns collected under one policy so they can be used to estimate performance under a different policy.

This approach is powerful because it allows us to evaluate risky, expensive, or multiple candidate policies without needing to execute them directly.

The lecture concludes with a practical example using a logged dataset of four episodes, where two different candidate policies (π_A and π_B) are evaluated without ever being run in the environment.

في On-Policy Monte Carlo (MC) يتم استخدام نفس السياسة للتفاعل مع البيئة والتعلم منها، وهو ما قد يشكل قيدًا في العديد من التطبيقات الواقعية.

تقدم هذه المحاضرة مفهومين أساسيين:

• سياسة السلوك (Behavior Policy - b): وهي السياسة المستخدمة فعليًا لجمع البيانات والتفاعل مع البيئة.
• السياسة المستهدفة (Target Policy - π): وهي السياسة التي نرغب في تقييمها أو التعلم عنها.

بعد ذلك، يتعرف الطلاب على مفهوم Importance Sampling، وهي تقنية تقوم بإعادة وزن (Reweighting) العوائد التي تم جمعها باستخدام سياسة معينة، بحيث يمكن استخدامها لتقدير أداء سياسة مختلفة.

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

وتختتم المحاضرة بمثال عملي يعتمد على مجموعة بيانات مسجلة تتكون من أربع حلقات (Episodes)، حيث يتم تقييم سياستين مختلفتين (π_A و π_B) دون تشغيلهما فعليًا داخل البيئة.

This lecture brings everything together through a complete hands-on implementation of First-Visit Monte Carlo Control using the Blackjack-v1 environment.

Students will build and train an RL agent from scratch, applying the concepts learned throughout the section in a real environment.

After training for approximately 500,000 episodes, students should observe:

• A win rate of around 42%
• Approximately 200 evaluated states
• A clear 3D value surface that closely resembles real Blackjack strategy tables

This lecture represents the “you can actually build RL systems now” milestone — where theory turns into practical implementation and visible results.

في هذه المحاضرة تتجمع جميع المفاهيم معًا من خلال تنفيذ عملي كامل لخوارزمية First-Visit Monte Carlo Control باستخدام بيئة Blackjack-v1.

سيقوم الطلاب ببناء وتدريب وكيل تعلم معزز من الصفر، مع تطبيق جميع المفاهيم التي تم تعلمها خلال هذا القسم داخل بيئة حقيقية.

بعد التدريب على حوالي 500,000 حلقة (Episode)، من المتوقع أن يلاحظ الطلاب:

• معدل فوز يقارب 42%
• حوالي 200 حالة تم تقييمها
• ظهور سطح قيم ثلاثي الأبعاد (3D Value Surface) يشبه بشكل كبير جداول استراتيجيات لعبة البلاك جاك الحقيقية

تمثل هذه المحاضرة لحظة “أصبح بإمكانك فعل ذلك فعليًا” — حيث تتحول المفاهيم النظرية إلى تطبيق عملي ونتائج ملموسة.

This lecture introduces TD(0) — Temporal Difference Learning, one of the simplest yet most influential algorithms in Reinforcement Learning (RL).

Unlike Monte Carlo methods, which wait until the end of an episode before updating value estimates, TD(0) learns immediately after every step by comparing the current prediction with the next prediction.

Students will learn:

• The TD(0) update rule and how it works.
• The meaning of every symbol in the equation.
• How learning happens through prediction errors between consecutive states.

To make the concept intuitive, the lecture walks through a 3-state random walk example by hand, showing step by step how rewards gradually propagate backward through the states — one step at a time across episodes.

This lecture marks an important transition toward online learning, where agents improve continuously while interacting with the environment.

تقدم هذه المحاضرة خوارزمية TD(0) — التعلم بالفروق الزمنية (Temporal Difference Learning)، والتي تُعد من أبسط وأكثر خوارزميات التعلم المعزز تأثيرًا وأهمية.

على عكس طرق مونت كارلو (Monte Carlo) التي تنتظر نهاية الحلقة (Episode) لتحديث قيم الحالات، تقوم TD(0) بالتعلم بعد كل خطوة مباشرة من خلال مقارنة التوقع الحالي بالتوقع التالي.

سيتعلم الطلاب:

• قاعدة التحديث الخاصة بـ TD(0) وكيفية عملها.
• معنى كل رمز داخل المعادلة.
• كيف يحدث التعلم من خلال أخطاء التنبؤ بين الحالات المتتالية.

ولتوضيح الفكرة عمليًا، تستعرض المحاضرة مثالًا يدويًا باستخدام ممر عشوائي مكوّن من 3 حالات (3-State Random Walk)، حيث يتم شرح كيفية انتقال المكافآت تدريجيًا إلى الخلف عبر الحالات — خطوة واحدة في كل حلقة.

تمثل هذه المحاضرة انتقالًا مهمًا نحو مفهوم التعلم أثناء التفاعل (Online Learning)، حيث يتحسن الوكيل باستمرار أثناء تعامله مع البيئة.

TD(0) is slow: the +1 reward propagates only one step per episode. Eligibility traces are a memory mechanism — each state keeps a fading record of how recently it was visited, and when a TD error fires it broadcasts to all states proportional to their trace. This single change lets one TD error update many states at once, solving the credit-assignment problem. We end by introducing the forward view (clean math) and the backward view (works online).

TD(0) uses just one real reward and one bootstrap; Monte Carlo uses all real rewards and no bootstrap. n-step TD is the family in between: collect n real rewards, then bootstrap. By tuning n you move smoothly between TD(0) (n=1) and MC (n=∞). We define the n-step return G^(n), give the update rule, and walk through TD(0) vs 3-step TD on the same trajectory so you can see credit assignment speed up.

TD(0) and Monte Carlo make opposite mistakes. TD(0) is biased (its bootstrap V is wrong early on) but has low variance (updates are consistent). MC is unbiased (uses real returns) but has high variance (rollouts differ wildly). This lecture frames the trade-off, draws the bullseye picture, sketches the U-shaped total-error curve, and finishes with a concrete numerical example comparing TD(0), TD(3), and MC across 5 simulated episodes — TD(3) wins on MSE.

TD(λ) is the synthesis of Lectures 2 and 3: combine eligibility traces (Lec 2) with multi-step returns (Lec 3) into one update with a single tuning knob λ. The forward view blends all n-step returns with geometric weights (1−λ)λ^(n−1); the backward view achieves the same updates online via traces decaying by γλ. We clarify the common confusion (TD(λ=1) is NOT TD(n=1) — it's roughly MC), look at the λ-weights for three values of λ, and walk through computing a λ-return by hand.

We move from prediction (estimating V) to control (finding the optimal policy). SARSA is one-step TD applied to Q(s,a), using the policy's own next-action sample — making it on-policy. We derive the SARSA update, walk through it on a tiny 2-state grid, then merge it with eligibility traces to get SARSA(λ) — the capstone algorithm that combines everything in Section 4. A worked example shows how a single TD error broadcasts to three Q-values via traces.

A short connective lecture that places everything you've learned on a single map and previews the Intermediate course. The unification map shows where TD, SARSA, MC, and DP each sit on the model-free / model-based axis and points to the next steps: Q-learning, DQN, policy gradients, actor-critic, PPO.