Lecture 1: Introduction to Reinforcement Learning

Lecture 1: Introduction to Reinforcement

Learning

David Silver
Lecture 1: Introduction to Reinforcement Learning

Outline

1 Admin

2 About Reinforcement Learning

3 The Reinforcement Learning Problem

4 Inside An RL Agent

5 Problems within Reinforcement Learning

Lecture 1: Introduction to Reinforcement Learning
Admin

Class Information

Thursdays 9:30 to 11:00am

Website:
http://www.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html
Group:
http://groups.google.com/group/csml-advanced-topics
Contact me: [email protected]
Lecture 1: Introduction to Reinforcement Learning
Admin

Assessment

Assessment will be 50% coursework, 50% exam

Coursework
Assignment A: RL problem
Assignment B: Kernels problem
Assessment = max(assignment1, assignment2)
Examination
A: 3 RL questions
B: 3 kernels questions
Answer any 3 questions
Lecture 1: Introduction to Reinforcement Learning
Admin

Textbooks

An Introduction to Reinforcement Learning, Sutton and

Barto, 1998
MIT Press, 1998
40 pounds
Available free online!
http://webdocs.cs.ualberta.ca/sutton/book/the-book.html
Algorithms for Reinforcement Learning, Szepesvari
Morgan and Claypool, 2010
20 pounds
Available free online!

http://www.ualberta.ca/szepesva/papers/RLAlgsInMDPs.pdf
Lecture 1: Introduction to Reinforcement Learning
About RL

Many Faces of Reinforcement Learning

Computer Science

Engineering Neuroscience
Machine
Learning
Optimal Reward
Control System
Reinforcement
Learning
Operations Classical/Operant
Research Conditioning
Bounded
Mathematics Psychology
Rationality

Economics
Lecture 1: Introduction to Reinforcement Learning
About RL

Branches of Machine Learning

Supervised Unsupervised
Learning Learning

Machine
Learning

Reinforcement
Learning
Lecture 1: Introduction to Reinforcement Learning
About RL

Characteristics of Reinforcement Learning

What makes reinforcement learning different from other machine

learning paradigms?
There is no supervisor, only a reward signal
Feedback is delayed, not instantaneous
Time really matters (sequential, non i.i.d data)
Agents actions affect the subsequent data it receives
Lecture 1: Introduction to Reinforcement Learning
About RL

Examples of Reinforcement Learning

Fly stunt manoeuvres in a helicopter

Defeat the world champion at Backgammon
Manage an investment portfolio
Control a power station
Make a humanoid robot walk
Play many different Atari games better than humans
Lecture 1: Introduction to Reinforcement Learning
About RL

Helicopter Manoeuvres
Lecture 1: Introduction to Reinforcement Learning
About RL

Bipedal Robots
Lecture 1: Introduction to Reinforcement Learning
About RL

Atari
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
Reward

Rewards

A reward Rt is a scalar feedback signal

Indicates how well agent is doing at step t
The agents job is to maximise cumulative reward
Reinforcement learning is based on the reward hypothesis
Definition (Reward Hypothesis)
All goals can be described by the maximisation of expected
cumulative reward
Do you agree with this statement?
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
Reward

Examples of Rewards
Fly stunt manoeuvres in a helicopter
+ve reward for following desired trajectory
ve reward for crashing
Defeat the world champion at Backgammon
+/ve reward for winning/losing a game
Manage an investment portfolio
+ve reward for each $ in bank
Control a power station
+ve reward for producing power
ve reward for exceeding safety thresholds
Make a humanoid robot walk
+ve reward for forward motion
ve reward for falling over
Play many different Atari games better than humans
+/ve reward for increasing/decreasing score
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
Reward

Sequential Decision Making

Goal: select actions to maximise total future reward

Actions may have long term consequences
Reward may be delayed
It may be better to sacrifice immediate reward to gain more
long-term reward
Examples:
A financial investment (may take months to mature)
Refuelling a helicopter (might prevent a crash in several hours)
Blocking opponent moves (might help winning chances many
moves from now)
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
Environments

Agent and Environment

observation action

Ot At

reward Rt
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
Environments

Agent and Environment

observation action

Ot At At each step t the agent:

Executes action At
Receives observation Ot
reward Rt
Receives scalar reward Rt
The environment:
Receives action At
Emits observation Ot+1
Emits scalar reward Rt+1
t increments at env. step
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

History and State

The history is the sequence of observations, actions, rewards

Ht = O1 , R1 , A1 , ..., At1 , Ot , Rt

i.e. all observable variables up to time t

i.e. the sensorimotor stream of a robot or embodied agent
What happens next depends on the history:
The agent selects actions
The environment selects observations/rewards
State is the information used to determine what happens next
Formally, state is a function of the history:

St = f (Ht )
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Environment State

observation action The environment state Ste is

Ot At the environments private
representation
i.e. whatever data the
reward Rt environment uses to pick the
next observation/reward
The environment state is not
usually visible to the agent
Even if Ste is visible, it may
contain irrelevant
environment state Set
information
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Agent State
The agent state Sta is the
agent state Sat
agents internal
representation
observation action

Ot At
i.e. whatever information
the agent uses to pick the
next action
reward Rt i.e. it is the information
used by reinforcement
learning algorithms
It can be any function of
history:

Sta = f (Ht )
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Information State
An information state (a.k.a. Markov state) contains all useful
information from the history.
Definition
A state St is Markov if and only if

P[St+1 | St ] = P[St+1 | S1 , ..., St ]

The future is independent of the past given the present

H1:t St Ht+1:
Once the state is known, the history may be thrown away
i.e. The state is a sufficient statistic of the future
The environment state Ste is Markov
The history Ht is Markov
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Rat Example

What if agent state = last 3 items in sequence?

What if agent state = counts for lights, bells and levers?
What if agent state = complete sequence?
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Fully Observable Environments

Full observability: agent directly

state action observes environment state
St At
Ot = Sta = Ste

reward Rt
Agent state = environment
state = information state
Formally, this is a Markov
decision process (MDP)
(Next lecture and the
majority of this course)
Lecture 1: Introduction to Reinforcement Learning
The RL Problem
State

Partially Observable Environments

Partial observability: agent indirectly observes environment:

A robot with camera vision isnt told its absolute location
A trading agent only observes current prices
A poker playing agent only observes public cards
Now agent state 6= environment state
Formally this is a partially observable Markov decision process
(POMDP)
Agent must construct its own state representation Sta , e.g.
Complete history: Sta = Ht
Beliefs of environment state: Sta = (P[Ste = s 1 ], ..., P[Ste = s n ])
Recurrent neural network: Sta = (St1
a
Ws + Ot Wo )
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Major Components of an RL Agent

An RL agent may include one or more of these components:

Policy: agents behaviour function
Value function: how good is each state and/or action
Model: agents representation of the environment
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Policy

A policy is the agents behaviour

It is a map from state to action, e.g.
Deterministic policy: a = (s)
Stochastic policy: (a|s) = P[At = a|St = s]
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Value Function

Value function is a prediction of future reward

Used to evaluate the goodness/badness of states
And therefore to select between actions, e.g.

v (s) = E Rt+1 + Rt+2 + 2 Rt+3 + ... | St = s

Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Example: Value Function in Atari

Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Model

A model predicts what the environment will do next

P predicts the next state
R predicts the next (immediate) reward, e.g.
a 0
Pss 0 = P[St+1 = s | St = s, At = a]

Ras = E [Rt+1 | St = s, At = a]
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Maze Example

Start
Rewards: -1 per time-step
Actions: N, E, S, W
States: Agents location
Goal
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Maze Example: Policy

Start

Goal

Arrows represent policy (s) for each state s

Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Maze Example: Value Function

-14 -13 -12 -11 -10 -9

Start -16 -15 -12 -8

-16 -17 -6 -7

-18 -19 -5

-24 -20 -4 -3

-23 -22 -21 -22 -2 -1 Goal

Numbers represent value v (s) of each state s

Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Maze Example: Model

-1 -1 -1 -1 -1 -1 Agent may have an internal

Start -1 -1 -1 -1 model of the environment
-1 -1 -1 Dynamics: how actions
-1 change the state
-1 -1 Rewards: how much reward
-1 -1 Goal
from each state
The model may be imperfect

a
Grid layout represents transition model Pss 0

Numbers represent immediate reward Ras from each state s

(same for all a)
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Categorizing RL agents (1)

Value Based
No Policy (Implicit)
Value Function
Policy Based
Policy
No Value Function
Actor Critic
Policy
Value Function
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

Categorizing RL agents (2)

Model Free
Policy and/or Value Function
No Model
Model Based
Policy and/or Value Function
Model
Lecture 1: Introduction to Reinforcement Learning
Inside An RL Agent

RL Agent Taxonomy

Model-Free

Value Function Actor Policy

Critic

Value-Based Policy-Based

Model-Based

Model
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Learning and Planning

Two fundamental problems in sequential decision making

Reinforcement Learning:
The environment is initially unknown
The agent interacts with the environment
The agent improves its policy
Planning:
A model of the environment is known
The agent performs computations with its model (without any
external interaction)
The agent improves its policy
a.k.a. deliberation, reasoning, introspection, pondering,
thought, search
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Atari Example: Reinforcement Learning

observation action

Ot At
Rules of the game are
unknown
reward Rt
Learn directly from
interactive game-play
Pick actions on
joystick, see pixels
and scores
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Atari Example: Planning

Rules of the game are known

Can query emulator
right left
perfect model inside agents brain
If I take action a from state s:
what would the next state be?
what would the score be? right left right left

Plan ahead to find optimal policy

e.g. tree search
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Exploration and Exploitation (1)

Reinforcement learning is like trial-and-error learning

The agent should discover a good policy
From its experiences of the environment
Without losing too much reward along the way
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Exploration and Exploitation (2)

Exploration finds more information about the environment

Exploitation exploits known information to maximise reward
It is usually important to explore as well as exploit
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Examples

Restaurant Selection
Exploitation Go to your favourite restaurant
Exploration Try a new restaurant
Online Banner Advertisements
Exploitation Show the most successful advert
Exploration Show a different advert
Oil Drilling
Exploitation Drill at the best known location
Exploration Drill at a new location
Game Playing
Exploitation Play the move you believe is best
Exploration Play an experimental move
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Prediction and Control

Prediction: evaluate the future

Given a policy
Control: optimise the future
Find the best policy
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Gridworld Example: Prediction

A B 3.3 8.8 4.4 5.3 1.5

+5 1.5 3.0 2.3 1.9 0.5
+10 B 0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

Actions
A -1.9 -1.3 -1.2 -1.4 -2.0

(a) (b)
What is the value function for the uniform random policy?
Lecture 1: Introduction to Reinforcement Learning
Problems within RL

Gridworld Example: Control

A B 22.0 24.4 22.0 19.4 17.5

+5 19.8 22.0 19.8 17.8 16.0

+10 B 17.8 19.8 17.8 16.0 14.4

16.0 17.8 16.0 14.4 13.0

A 14.4 16.0 14.4 13.0 11.7

a) gridworld v
b) V* c) *

What is the optimal value function over all possible policies?

What is the optimal policy?
Lecture 1: Introduction to Reinforcement Learning
Course Outline

Course Outline

Part I: Elementary Reinforcement Learning

1 Introduction to RL
2 Markov Decision Processes
3 Planning by Dynamic Programming
4 Model-Free Prediction
5 Model-Free Control
Part II: Reinforcement Learning in Practice
1 Value Function Approximation
2 Policy Gradient Methods
3 Integrating Learning and Planning
4 Exploration and Exploitation
5 Case study - RL in games