Reinforcement Learning

Dr. Md, Asraful Haque

AMU, Aligarh
What’s Reinforcement Learning?
• Supervised (inductive) learning is the simplest and most studied type
of learning
• How can an agent learn behaviors when it doesn’t have a teacher to
tell it how to perform?
− The agent has a task to perform
− It takes some actions in the world
− At some later point, it gets feedback telling it how well it did on performing
the task
− The agent learns from the feedback and performs the task efficiently
• This problem is called reinforcement learning:
− The agent gets positive reinforcement for tasks done well
− The agent gets negative reinforcement for tasks done poorly
What’s Reinforcement Learning?

• Agent interacts with an environment and learns how to maximize reward

signal to achieve some long-term goal.
• Agent must be able to partially/fully sense the environment state and take
actions to influence the environment state.
• The state is typically described with a feature-vector
RL: Agent & Environment
• We reinforce the agent to learn to perform the best actions by experience.
This is the strategy or policy.
• The agent arrives at different scenarios known as states by performing
actions. Actions lead to rewards which could be positive and negative.
• We want the agent to earn lots of reward.
• The agent must prefer past actions that have been found to be effective at
producing reward.
• The agent must explore actions to make better action selections in the
future.
• Trade-off between exploration and exploitation.
RL System Components
RL System Components
Key Features of Reinforcement Learning
• In RL, the agent is not instructed about the environment and what
actions need to be taken.
• It is based on the hit and trial process.
• The agent takes the next action and changes states according to the
feedback of the previous action.
• The agent may get a delayed reward.
• The environment is stochastic, and the agent needs to explore it to
reach to get the maximum positive rewards.
Reward Maximization
Markov Decision Process: Shortest Path Problem
Markov Decision Process
• The Markov Decision Process (MDP) is a mathematical framework used to
model decision-making problems in the context of reinforcement learning.
• MDPs are a tool for modeling sequential decision-making problems where an agent
interacts with an environment in a sequential fashion.
• Markov Property:
• 𝑝(𝑠 ′ , 𝑟|𝑠, 𝑎) completely characterizes the environment’s dynamics.
• The state captures all relevant information from history.
• Once the state is known, the history may be thrown away.
• The state is a sufficient statistic of the past.
MDP
• In figure, given an MDP, at the timestep t, the environment’s state is 𝑆𝑡 and the agent
chooses an action 𝐴𝑡. This action will make a transition according to the dynamics
of environment, 𝑝(𝑠′,𝑟|𝑠,𝑎). Then, at timestep t+1, the agent observes the next state
𝑆𝑡+1 and reward 𝑅𝑡+1, chooses a new action 𝐴𝑡+1, and the process is repeated. The
goal of the agent is to find a way of choosing the actions so as to maximize the
expected total discounted reward, based on the observed history.
MDP
• The general goal of reinforcement learning is to maximize the overall
return by selecting appropriate actions during the interaction.
• Return at t: the sum of the rewards received after timestep t (from t+1
to T, T is the final time step)

• Discount rate: 𝛾 ∈ [0,1]. A small discount rate gives less weights of

future rewards towards the return. There are two extreme cases:
1. only immediate reward (𝑅𝑡+1) is counted when 𝛾 = 0;
2. all rewards are equally counted when 𝛾 = 1.
MDP Example:
(Volcano Crossing)

• As shown in Fig, the land is divided into 3x4 grid cells: (x,y), x=1,2,3 and y=1,2,3,4. The
volcano is located in the cells (1,3) and (2,3). There are two island cells (3,1) and (1,4). An
agent travels on the land. The agent can move in four directions: east (E), south (S), west (W),
and north (N). If the agent tries to move off the grid, it remains in the same cell. The number
in each cell represents the reward when the agent moves to it. The rewards are zero for the
cell without a number. For example, if the agent moves to any volcano cell (either (1,3) or
(2,3)), it receives -50 reward. If the agent moves to the island cell (1,4), a reward of 20 is
received. Although the agent can select the moving direction, the agent slips with a
probability p when moving. If it slips, it will move randomly in one of the four directions. If
it does not slip (with a probability of 1-p), it will go to the cell it intends for. Whenever the
agent reaches any island or volcano cell, the travel ends.
MDP Example:
(Volcano Crossing)
• The question is: how should the agent select a moving direction given its current location so
that it can get a maximal return for the travel in average sense? Without the loss of generality,
we can assume the agent starts at cell (1,1) and discount rate 𝛾=1 . A further question is:
should the agent try to move to the island (3,1) for a reward of 2 or to move to the island (1,4)
for a larger reward of 20 but with a bigger risk of slipping into volcano? We will revisit these
questions later.
• In this example, the state is the location of the agent (x,y). Action set 𝒜={𝐸,𝑆,𝑊,𝑁}. The
dynamics of the MDP is defined by 𝑝(𝑠′,𝑟|𝑠,𝑎)≡𝑃𝑟{𝑆𝑡=𝑠′,𝑅𝑡=𝑟|𝑆𝑡−1=𝑠,𝐴𝑡−1=𝑎}.
• For example, by assuming slipping probability p=0.1, 𝑝((1,1),0|(1,1),𝐸)=0.1×(1/4+1/4)=0.05.
This probability means that when the agent selects an action E at the state (1,1), the agent will
stay at the same place (1,1) with a reward of 0 with a probability of 0.05. Note that even
though it selects E, there is a chance for slipping to occur. When slipping occurs, it could
move E,S,W,N with a probability of ¼ for each direction, and W and N will lead the agent to
stay. You can verify 𝑝((1,4),20|(2,4),𝑁)=0.9+0.1×1/4=0.925.
Policy
• The behavior of the agent is described by a policy specifying a
mapping from states to actions being selected by the agent. Thus, the
policy is not the property of the environment, but the behavior of the
agent. A deterministic stationary policy can be defined by a mapping
π, which maps states to actions, 𝑎=𝜋(𝑠).
• More generally, a stochastic stationary policy is defined by the
probability distribution of selecting each possible action, denoted as 𝜋(
𝑎|𝑠). This implies that, at timestep t, 𝜋(𝑎|𝑠) is the probability that 𝐴𝑡=𝑎
if 𝑆𝑡=𝑠. In general, a policy is probabilistic, instead of deterministic.
Value function
• The reward signal indicates what is good in the short run while the
value function indicates what is good in the long run.
• The value of a state is the total amount of reward an agent can expect
to accumulate in that state.
• Action choices are made based on value judgements.
• Rewards are given directly by the environment.
• Values must continually be re-estimated from the sequence of
observations that an agent makes over its lifetime.
Types of Value function
• There are two types of value functions: state-value function and action-
value function. A value function is defined in terms of future expected
return starting from a state or a state-action pair, by following a policy 𝜋.
1. State-value function is defined as the expectation value of future total
return given a current state s and a policy 𝜋.

2. Action-value function is defined as the expectation value of future total

return give a current state s and action, plus a policy 𝜋.
Bellman Equation
• According to the Bellman Equation, long-term- reward in a given action is
equal to the reward from the current action combined with the expected
reward from the future actions taken at the following time.
• Bellman equation decomposes the value function into two parts, the
immediate reward plus the discounted future values.
Example
• Recall the volcano crossing MDP. The
state is represented by the location of the
agent, (x,y). Suppose that the agent
selects the path toward the island with a
reward of 20, indicated by the blue
arrows in Fig. However, even if the agent
selects one moving direction, it may slip
with a probability of p, instead of moving
in the selected direction. When a slip
occurs, the agent will randomly move
into its adjacent cell with equal
probability (1/4), indicated by the red line
arrows. Thus, the real policy 𝜋(𝑎|𝑠) can
be obtained based on the selected path
and the location of the agent.
Example
• For example, consider s=(1,1), we have the policy for this state (location)
State-Value Function
• To find the state-value function, we first
define the state values for the states V1,
V2, …., V8, as shown in Fig., and then
write one Bellman equation for each
state. For instance, the Bellman equation
for state (1,1) is:
State-Value Function
• The first term in the right side of the equation corresponds to the intentional
moving from V1 to V2. The second term accounts for slipping randomly to
four directions. Recall that if the agent tries to move off the grid, it remains
in the same cell. The Bellman equation for state (2,4) is:

• In total, we can have totally 8 equations for the 8 states and get the state-
value function by solving these 8 linear equations.
State-Value Function
• The solutions are shown in Fig. • Following fig. shows the state
for p=0.1. values for a policy of complete
random move at all states (i.e., p=1).
Timid (coward) Policy
• Now, consider a coward (timid) policy, the agent tries to avoid slipping into
volcano as possible as it can, regardless of a big reward 20 in the island. The
resulting state values are shown in Fig.(right-side).
Optimal Policy
• The state-value function depends on the policy adopted by the agent.
• The policy π is said to be better (or equal) than 𝜋′ (i.e., 𝜋≥𝜋′) if and only if
𝑣𝜋(𝑠) ≥ 𝑣𝜋′(𝑠) for all 𝑠∈𝒮.
• For an MDP, there is always at least one policy that is better than or equal to
all other policies.
• This best policy is called an optimal policy, denoted as 𝜋∗, and the
corresponding state-value function is the optimal state-value function,
defined as:
Optimal Policy
• Similarly, the optimal action function is defined as:
Types of RL Algorithms
RL algorithms can be divided into two categories – model-based and model-free.
• Model-based, as it sounds, has an agent trying to understand its environment and
creating a model for it based on its interactions with this environment. In such a
system, preferences take priority over the consequences of the actions i.e. the
greedy agent will always try to perform an action that will get the maximum
reward irrespective of what that action may cause.
• Model-free algorithms seek to learn the consequences of their actions through
experience via algorithms such as Policy Gradient, Q-Learning, etc. In other
words, such an algorithm will carry out an action multiple times and will adjust
the policy (the strategy behind its actions) for optimal rewards, based on the
outcomes.
Types of RL Algorithms
• If the agent can predict the reward for some action before actually performing it
thereby planning what it should do, the algorithm is model-based. While if it
actually needs to carry out the action to see what happens and learn from it, it is
model-free.
• This results in different applications for these two classes, for e.g. a model-based
approach may be the perfect fit for playing chess or for a robotic arm in the
assembly line of a product, where the environment is static and getting the task
done most efficiently is our main concern. However, in the case of real-world
applications such as self-driving cars, a model-based approach might prompt the
car to run over a pedestrian to reach its destination in less time (maximum
reward), but a model-free approach would make the car wait till the road is clear
(optimal way out).
Q-Learning
• Q-learning is a model-free reinforcement learning algorithm to learn
the value of an action in a particular state.
• In realistic situations, we cannot possibly learn about every single
state!
• Instead, we want to generalize:
Learn about some small number of training states from experience
Generalize that experience to new, similar states
This is a fundamental idea in machine learning, and we’ll see it over and over
again
Q-Learning
• Full reinforcement learning
You don’t know the transitions T(s,a,s’)
You don’t know the rewards R(s,a,s’)
You can choose any actions you like
Goal: learn the optimal policy
… what value iteration did!
• In this case:
Learner makes choices!
Fundamental trade-off: exploration vs. exploitation
This is NOT offline planning! You actually take actions in the world and find
out what happens…
Q-Learning Algorithm
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Q-Learning Example
Introduction to Deep Learning
• Deep learning is defined as the
subset of machine learning and
artificial intelligence that is
based on artificial neural
networks.
• In deep learning, the deep word
refers to the number of layers in
a neural network.
• It lessens the need for
feature engineering.
Background
• Traditional ML models use hand-crafted features and relatively simple
trainable classifier.
• It is very tedious and costly to develop handcrafted features.
• The handcrafted features are usually highly dependents on one
application, and cannot be transferred easily to other applications.
Deep Learning
• Deep learning seeks to learn rich hierarchical representations (i.e.
features) automatically through multiple stage of feature learning process.
Learning Hierarchical Representations
• Hierarchy of representations with increasing level of abstraction.
• Each stage is a kind of trainable nonlinear feature transform.
• Image recognition
Pixel → edge → texton → motif → part → object
• Text
Character → word → word group → clause → sentence →
story
Hierarchical Representations
What exactly is deep learning ?
• ‘Deep Learning’ means using a neural network with several layers of
nodes between input and output.
 Multilayer neural networks have been around for 25 years. What’s
actually new?
we have always had good algorithms for learning the weights in networks
with 1 hidden layer.
but these algorithms are not good at learning the weights for networks with
more hidden layers.
what’s new is: algorithms for training many layer networks.
Basic Structure of Deep Learning
• In deep learning, nothing is
programmed explicitly. Basically,
it is a machine learning class
that makes use of numerous
nonlinear processing units so as
to perform feature extraction as
well as transformation. The
output from each preceding
layer is taken as input by each
one of the successive layers.
How does Deep Learning work?
• The steps include in deep learning as follows:
1. Calculate the weighted sum
2. Use this weighted sum in step1 as input for the activation
function.
3. The activation function adds bias and decides whether the
neuron should be triggered or not.
4. Predict output at the output layer.
5. Compare predicted output and actual output and accordingly
use the backpropagation method for improving the performance
of the model. In this step, the cost function plays a vital role in
reducing the error rate.
Types of deep neural networks
• Feedforward neural network
• Recurrent neural network
• Multi-layer perceptron
• Convolution neural network (CNN)
• etc…..
Limitations of deep learning
• It only learns through the observations.
• It comprises of biases issues.
• It requires an ample amount of data.
• It is quite expensive to train.
• It does not have strong theoretical groundwork.