Dr. Khellat Kihel Souad

Machine Learning (ML)

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

Université des sciences et de la technologie Mohamed-Boudiaf, Oran.

​

Faculté des mathématiques et informatique

​

Département d'informatique

​

2

CHAPTER 5 (PART II) : REINFORCEMENT LEARNING�

3

PROBLEMATICS

4

5

6

7

INTRODUCTION TO REINFORCEMENT LEARNING

• – Automated acquisition of skills for decision-making (actions or control) in complex and uncertain environments.�– Learning through "experience" a behavioral strategy (called a policy) based on observed failures or successes (reinforcements or rewards).�– Examples: the hot-and-cold game, sensorimotor learning, chess, autonomous mobile robotics, planning, etc.�– Applications: autonomous robotics, economics, operations research, games, etc.

8

A MULTI-DICIPLINARY FIELD

9

INTRODUCTION

How to learn to navigate a maze without making mistakes?�Or, how to master a good strategy for:

• vacuuming a given room?
• operating the elevators in a skyscraper?

​

10

REINFORCEMENT LEARNING

• = Learning in a (partially) unknown environment�= Learning through trial and error�= Learning by interacting with the environment (exploration)�= Classification�→ Because the goal is to learn good sequences of actions�= Planning�→ Because the environment is only partially known�→ Because the environment can change�→ Because initial states and goals are often not fixed in advance

11

REINFORCEMENT LEARNING

• Objective: learning of a behavior strategy (a policy) which maximizes the long term sum of rewards (delayed reward) by a direct interaction (trial-and-error) with an unknown and uncertain (e.g., stochastic) environment.

12

GENERAL CASE

An agent operates in a given environment.�It can perform certain actions based on the current state:

The state of the environment, And its own internal state,�Leading to a transition to a new state.

• Some actions are associated with immediate rewards or costs.

​

​

​

​

• The agent must learn which action to choose in each state�in order to follow an optimal action sequence (i.e., one that maximizes its long-term advantage).

​

13

Reinforcement Learning:�A framework for adapting an agent to its environment by leveraging rewards/punishments (reinforcement signals).

14

KEY POINTS

Reinforcement Learning (RL) involves several fundamental concepts that define how machines learn from experience and make decisions:

• Agent: The decision-maker that interacts with its environment.
• Environment: The external system the agent interacts with.
• State: A representation of the current situation of the environment.
• Action: A choice the agent can make in a given state.
• Reward: Immediate feedback the agent receives after performing an action in a state.
• Policy: A set of rules the agent follows to determine its actions based on states.
• Value Function: Estimates the long-term expected reward of a specific state under a given policy.

​

15

THE AGENT-ENVIRONMENT INTERACTION PROTOCOL

16

REINFORCEMENT LEARNING PROCESS

1. Set Up the Environment
• Define possible states (situations the agent can be in).
• List available actions (choices the agent can make).
• Determine transition rules (how actions change states).
• Assign rewards (feedback for good/bad actions).
2. Initialize the Agent
• Start with a simple policy (strategy for choosing actions).
• Set initial value estimates (predictions of future rewards).
3. Start Learning
• Observe the starting state (where the agent begins).
• Choose an action (based on current policy, sometimes randomly).
• See the result (new state + reward from the environment).
• Update the policy (improve decisions based on rewards).
4. Repeat & Improve Keep acting, observing, and updating. Over time, the agent learns the best actions for each state.

​

17

ENVIRONMENT

• Depending on how it reacts to the agents actions and how it can be perceived by the agent, we have :
• Fully controllable (e.g., chess), partially controllable (e.g., portfolio optimization)
• Deterministic (e.g., chess) or stochastic (e.g., backgammon)
• Adversarial (e.g., chess) or fixed (e.g., tetris)
• Fully observable (e.g., chess) or partially observable (e.g., robotics)
• Known (e.g., chess) or unknown (e.g., robotics)

18

THE CRITIC & AGENT

• The critic it returns the reinforcement, which evaluates the quality of the action taken by the agent depending on its actual state.
• The agent:
• defines the concept of state and action and it acts according to
• Open loop control
• Close loop control (i.e., adaptive)
• Non-stationary close loop control (i.e., learning)

19

MARKOV DECISION PROCESS

A Markov Decision Process (MDP) is a mathematical framework that provides a structured way to model environments in reinforcement learning.

An MDP is formally defined by the tuple (S, A, T, R, γ), where:

• States (S): The set of all possible states in the environment
• Actions (A): The set of all possible actions the agent can take
• Transition Model (T): The probability of transitioning from one state to another
• Reward Function (R): The immediate reward received after transitioning between states
• Discount Factor (γ): A value between 0 and 1 that determines the importance of future rewards

​

20

21

BELLMAN EQUATION

The Bellman equation computes the value of being in a state or taking an action based on expected future rewards.

It decomposes the total expected reward into:

1. Immediate reward (received after the current action)
2. Discounted future rewards (weighted by time preference)
1. This fundamental equation enables agents to make decisions that maximize long-term cumulative benefits.

​

22

23

Q-LEARNING ALGORITHM

Q-Learning is a model-free algorithm, meaning it doesn’t require prior knowledge of the environment’s dynamics (transition probabilities or reward structure). Instead, it learns by direct interaction with the environment.

• Core Objective:�Discover the optimal action-selection policy (denoted as π*) that maximizes the cumulative discounted reward over time.

​

24

KEY CONCEPT OF Q-LEARNING

1. Q-Value (Q(s,a))

• Definition: The expected cumulative reward for taking action a in state s, then following the optimal policy afterward.
• Purpose: Guides the agent to choose actions that maximize long-term rewards.

2. Q-Table

Structure: A lookup table storing Q-values for all possible (state, action) pairs.

Learning: Updated iteratively as the agent explores the environment.

​

25

26

3. Learning Rate (α, 0 ≤ α ≤ 1)

• Role: Controls how aggressively new experiences override old Q-values.
• α = 0: No learning (keeps old values).
• α = 1: Fully replaces past estimates with new data.
• Trade-off: High α adapts quickly but may overfit to recent experiences.

4. Discount Factor (γ, 0 ≤ γ < 1)

• Role: Determines the importance of future rewards:
• γ ≈ 0: Short-sighted (only cares about immediate rewards).
• γ ≈ 1: Far-sighted (prioritizes long-term outcomes).
• Example: If γ = 0.9, a reward of 10 after 3 steps is valued as 10 × (0.9³) ≈ 7.29 now.

​

Why These Matter

• The Q-table is the agent’s "cheat sheet" for decision-making.
• α and γ are hyperparameters tuned to balance speed vs. stability of learning.

​

27

28

29

Q LEARNING PROCESS

The Q-learning algorithm does not specify a fixed number of updates for the Q-table. Instead:

1. Exploration Phase: The agent repeatedly updates Q-values by interacting with the environment (trying random actions to discover rewards).
2. Exploitation Phase: The agent uses its current Q-table (even if imperfect) to take goal-directed actions.

Key Idea:

• This balance between learning (updating Q) and acting (using Q) continues until convergence or task completion.
• No predefined threshold—learning stops when Q-values stabilize or the task is solved.

​

30

SARSA

31

32

Ex : Agent sur une falaise (Cliff Walking)

• Q-learning : L'agent apprend à marcher au bord de la falaise (plus risqué mais optimal).
• SARSA : L’agent apprend à rester à l’écart pour éviter les chutes (plus sûr mais sous-optimal).

​