Reinforcement and Deep Learning Overview CHoogteijling
Reinforcement and Deep Learning
Contents
1 Finite Markov Decision Processes 2
1.1 The Agent-Environment Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Returns and Episodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Unified Notation for Episodic and Continuing Tasks . . . . . . . . . . . . . . . . . . . . . 3
1.5 Policies and Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Optimal Policies and Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . . 4
1.7 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Dynamic Programming 5
2.1 Policy Evaluation (Prediction) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Greedy Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4.1 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Monte Carlo Methods 9
3.1 Trade-off Exploitation and Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 Off-Policy Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Temporal-Difference Learning 15
5 Planning 17
5.1 n-step bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Planning and Learning with Tabular Methods . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.3 Prediction with Approximatfion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6 Deep Reinforcement Learning 20
6.1 Deep Q-learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 Policy Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.3 Actor-Critic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7 Reinforcement Learning from Human Feedback 24
7.1 Proximal Policy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 PPO Full Objective and Group Relative Policy Optimization . . . . . . . . . . . . . . . . 25
7.3 Direct Preference Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Images from Sutten & Barto 2020, Reinforcement Learning and lecture slides.
1
,Reinforcement and Deep Learning Overview CHoogteijling
Figure 1: The agent-environment interaction in a Markov decision process.
1 Finite Markov Decision Processes
The Markov Decision Process (MDP) framework is an abstraction of the problem of goal-directed learning
from interaction. Any problem can be reduced to three signals passing back and forth between an agent
and its environment:
• Actions: A signal that represents the choices made by the agent.
• States: A signal that represents the basis on which the choices are made.
• Rewards: A signal to define the agent’s goal.
In MDPs we estimate the value q∗ (s, a) of each action a in each state s, or we estimate the value v∗ (s)
of each state given optimal action selections. These state-dependent quantities are essential to accurately
assigning credit for long-term consequences to individual action selections.
1.1 The Agent-Environment Interface
• Agent: The learner and decision maker.
• Environment: The thing the agent interacts with, comprising everything outside the agent.
• Trajectory: A sequence of states, actions, and rewards, S0 , A0 , R1 , S1 , A1 , R2 , . . . .
• Finite MDP, the sets of states, actions, and rewards all have a finite number of elements.
• Markov property: The state must include information about all aspects of the past agent-
environment interaction that make a difference for the future.
At each timestep t, the agent receives some representation of the environment’s state, St ∈ S, and on
that basis selects an action, At ∈ A(s). One timestep later, the agent receives a numerical reward,
Rt+1 ∈ R ⊂ R, and finds itself in a new state St+1 . The probability function p : S × R × S × A → [0, 1] of
values occurring at time t, given particular values of the preceding state and actions defines the dynamics
of the MDP:
.
p(s′ , r | s, a) = P{St = s′ , Rt = r | St−1 = s, At−1 = a}
From the dynamics function p, we can compute the state-transition probabilities, expected reward
for state-action pairs, and expected rewards for state-action-next-state triples:
. X
p(s′ | s, a) = P{St = s′ | St−1 = s, At−1 = a} = p(s′ , r | s, a) state-transition probabilities
r∈R
. X X
r(s, a) = E[Rt | St−1 = s, At−1 = a] = r p(s′ , r | s, a) state-action pair
r∈R s′ ∈S
. X p(s′ , r | s, a)
r(s, a, s′ ) = E[Rt | St−1 = s, At−1 = a, St = s′ ] = r state-action-next-state triple
p(s′ | s, a)
r∈R
2
, Reinforcement and Deep Learning Overview CHoogteijling
1.2 Goals and Rewards
• Reward hypothesis: That all of what we mean by goals and purposes can be well thought of as
the maximization of the expected value of the cumulative sum of a received scalar signal (called
reward).
• The reward signal is a way of communication to the agent what you want achieved, not how you
want it achieved.
1.3 Returns and Episodes
In MDP the objective is to maximize the expected return. The return (Gt ) is defined as some specific
function of the reward sequence.
• Episode: A sequence of steps where the agent-environment interaction breaks naturally into sub-
sequences. The next episode starts independently of how the previous one ended.
• Terminal state: The end state of an episode.
• Episodic tasks: Tasks with episodes.
• Continuing tasks: A task where the agent-environment does not break naturally into identifiable
episodes, but goes on continually without limit. This makes forming the return more difficult as we
have T = ∞.
The return can be a simple function of the sum of the rewards. However, in continuing tasks this is
problematic as T = ∞. We use discounting, the agent tries to select actions so that the sum of the
discounted rewards it receives over the future is maximized.
Gt = Rt+1 + Rt+2 + · · · + RT simple return
∞
. X
Gt = Rt+1 + γRt+2 + γ 2 Rt+2 + · · · = γ k Rt+k+1 discounted return
k=0
• γ, 0 ≤ γ ≤ 1: discount rate. For continuing tasks γ < 1 is needed for convergence.
1.4 Unified Notation for Episodic and Continuing Tasks
We can describe both episodic and continuing tasks by adding an absorbing state to the episodic task.
The absorbing state is a state that only transitions to itself and generates only rewards of zero.
1.5 Policies and Value Functions
A policy is a mapping from states to probabilities of selecting each possible action. π(a | s) is the
probability that At = a if St = s. The value function (vπ (s), state-value-function) of a state s under a
policy π is the expected return when starting in s and following π. The action-value function qπ (s, a) is
the expected return starting from s, taking action a, and following policy π.
"∞ #
. X
vπ (s) = Eπ [Gt | St = s] = E γRt+k+1 | St = s , for all s ∈ S
k=0
"∞ #
. X
k
qπ (s, a) = Eπ [Gt | St = s, At = a] = Eπ γ Rt+k+1 | St = s, At = a
k=0
The Bellman equation expresses a relationship between the value of a state and the values of its
successor states. It averages over all the possibilities, weighting each by its probability of occurring. For
3
Reinforcement and Deep Learning
Contents
1 Finite Markov Decision Processes 2
1.1 The Agent-Environment Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Returns and Episodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Unified Notation for Episodic and Continuing Tasks . . . . . . . . . . . . . . . . . . . . . 3
1.5 Policies and Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.6 Optimal Policies and Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . . 4
1.7 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Dynamic Programming 5
2.1 Policy Evaluation (Prediction) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Greedy Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4.1 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Monte Carlo Methods 9
3.1 Trade-off Exploitation and Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 Off-Policy Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Temporal-Difference Learning 15
5 Planning 17
5.1 n-step bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Planning and Learning with Tabular Methods . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.3 Prediction with Approximatfion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6 Deep Reinforcement Learning 20
6.1 Deep Q-learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 Policy Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.3 Actor-Critic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7 Reinforcement Learning from Human Feedback 24
7.1 Proximal Policy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 PPO Full Objective and Group Relative Policy Optimization . . . . . . . . . . . . . . . . 25
7.3 Direct Preference Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Images from Sutten & Barto 2020, Reinforcement Learning and lecture slides.
1
,Reinforcement and Deep Learning Overview CHoogteijling
Figure 1: The agent-environment interaction in a Markov decision process.
1 Finite Markov Decision Processes
The Markov Decision Process (MDP) framework is an abstraction of the problem of goal-directed learning
from interaction. Any problem can be reduced to three signals passing back and forth between an agent
and its environment:
• Actions: A signal that represents the choices made by the agent.
• States: A signal that represents the basis on which the choices are made.
• Rewards: A signal to define the agent’s goal.
In MDPs we estimate the value q∗ (s, a) of each action a in each state s, or we estimate the value v∗ (s)
of each state given optimal action selections. These state-dependent quantities are essential to accurately
assigning credit for long-term consequences to individual action selections.
1.1 The Agent-Environment Interface
• Agent: The learner and decision maker.
• Environment: The thing the agent interacts with, comprising everything outside the agent.
• Trajectory: A sequence of states, actions, and rewards, S0 , A0 , R1 , S1 , A1 , R2 , . . . .
• Finite MDP, the sets of states, actions, and rewards all have a finite number of elements.
• Markov property: The state must include information about all aspects of the past agent-
environment interaction that make a difference for the future.
At each timestep t, the agent receives some representation of the environment’s state, St ∈ S, and on
that basis selects an action, At ∈ A(s). One timestep later, the agent receives a numerical reward,
Rt+1 ∈ R ⊂ R, and finds itself in a new state St+1 . The probability function p : S × R × S × A → [0, 1] of
values occurring at time t, given particular values of the preceding state and actions defines the dynamics
of the MDP:
.
p(s′ , r | s, a) = P{St = s′ , Rt = r | St−1 = s, At−1 = a}
From the dynamics function p, we can compute the state-transition probabilities, expected reward
for state-action pairs, and expected rewards for state-action-next-state triples:
. X
p(s′ | s, a) = P{St = s′ | St−1 = s, At−1 = a} = p(s′ , r | s, a) state-transition probabilities
r∈R
. X X
r(s, a) = E[Rt | St−1 = s, At−1 = a] = r p(s′ , r | s, a) state-action pair
r∈R s′ ∈S
. X p(s′ , r | s, a)
r(s, a, s′ ) = E[Rt | St−1 = s, At−1 = a, St = s′ ] = r state-action-next-state triple
p(s′ | s, a)
r∈R
2
, Reinforcement and Deep Learning Overview CHoogteijling
1.2 Goals and Rewards
• Reward hypothesis: That all of what we mean by goals and purposes can be well thought of as
the maximization of the expected value of the cumulative sum of a received scalar signal (called
reward).
• The reward signal is a way of communication to the agent what you want achieved, not how you
want it achieved.
1.3 Returns and Episodes
In MDP the objective is to maximize the expected return. The return (Gt ) is defined as some specific
function of the reward sequence.
• Episode: A sequence of steps where the agent-environment interaction breaks naturally into sub-
sequences. The next episode starts independently of how the previous one ended.
• Terminal state: The end state of an episode.
• Episodic tasks: Tasks with episodes.
• Continuing tasks: A task where the agent-environment does not break naturally into identifiable
episodes, but goes on continually without limit. This makes forming the return more difficult as we
have T = ∞.
The return can be a simple function of the sum of the rewards. However, in continuing tasks this is
problematic as T = ∞. We use discounting, the agent tries to select actions so that the sum of the
discounted rewards it receives over the future is maximized.
Gt = Rt+1 + Rt+2 + · · · + RT simple return
∞
. X
Gt = Rt+1 + γRt+2 + γ 2 Rt+2 + · · · = γ k Rt+k+1 discounted return
k=0
• γ, 0 ≤ γ ≤ 1: discount rate. For continuing tasks γ < 1 is needed for convergence.
1.4 Unified Notation for Episodic and Continuing Tasks
We can describe both episodic and continuing tasks by adding an absorbing state to the episodic task.
The absorbing state is a state that only transitions to itself and generates only rewards of zero.
1.5 Policies and Value Functions
A policy is a mapping from states to probabilities of selecting each possible action. π(a | s) is the
probability that At = a if St = s. The value function (vπ (s), state-value-function) of a state s under a
policy π is the expected return when starting in s and following π. The action-value function qπ (s, a) is
the expected return starting from s, taking action a, and following policy π.
"∞ #
. X
vπ (s) = Eπ [Gt | St = s] = E γRt+k+1 | St = s , for all s ∈ S
k=0
"∞ #
. X
k
qπ (s, a) = Eπ [Gt | St = s, At = a] = Eπ γ Rt+k+1 | St = s, At = a
k=0
The Bellman equation expresses a relationship between the value of a state and the values of its
successor states. It averages over all the possibilities, weighting each by its probability of occurring. For
3
