ML for Robotics
Duration: 120 min BCSE424L Dr. Harini S
Module 5: Reinforcement
Learning
• Peter Bodík, UC Berkely
• [Link]
Module Overview
•Basics of RL
• RL Framework
• Markov Decision Process
•Exploration Vs Exploitation
What’s Reinforcement
Session Overview Learning?
• Reinforcement learning
• more general than supervised/unsupervised learning
• learn from interaction w/ environment to achieve a goal
environment
reward
action
new state
agent
ExampleOverview
Session
Robot in a room actions: UP, DOWN,
LEFT, RIGHT
+1
-1 UP
START
80% move UP
10% move LEFT
• reward +1 at [4,3], -1 at [4,2] 10% move RIGHT
• reward -0.04 for each step
• what’s the strategy to achieve max reward?
• what if the actions were deterministic?
Other examples
• pole-balancing
• TD-Gammon [Gerry Tesauro]
• helicopter [Andrew Ng]
• no teacher who would say “good” or “bad”
• is reward “10” good or bad?
• rewards could be delayed
• similar to control theory
• more general, fewer constraints
• explore the environment and learn from experience
• not just blind search, try to be smart about it
Core Components of RL Framework in ML
Reinforcement Learning revolves around the idea that an agent (the learner or decision-
maker) interacts with an environment to achieve a goal. The agent performs actions and
receives feedback to optimize its decision-making over time.
•Agent: The decision-maker that performs actions.
•Environment: The world or system in which the agent operates.
•State: The situation or condition the agent is currently in.
•Action: The possible moves or decisions the agent can make.
•Reward: The feedback or result from the environment based on the agent’s action.
…Continued
• Policy
• Strategy used by the agent to choose actions
• Mapping :
• Value Function (V / Q)
• Measures how good a state or action is
• Helps in choosing long-term beneficial actions
• Episode
• A complete sequence from start to end
• Example: one full game
Markov Decision Process
• A Markov Decision Process (MDP) is the mathematical
foundation of Reinforcement Learning (RL)
• Objective of MDP :
• Property of MDP:
• The next state depends only on current state and action
RL Interaction Loop
1. Agent observes state (S)
2. Chooses action (A) using policy
3. Environment returns:
• New state (S′)
• Reward (R)
4. Agent updates its policy
5. Repeat
Mathematical Representation (MDP)
RL is often modeled using a Markov Decision Process (MDP):
Types of RL Methods
✓ Value-Based
• Learn value functions
• Example: Q-Learning
✓ Policy-Based
• Learn policy directly
• Example: Policy Gradient
✓ Actor-Critic
• Combination of both
Robot in a room
actions: UP, DOWN, LEFT, RIGHT
+1
UP
-1 80% move UP
10% move LEFT
10% move RIGHT
START
reward +1 at [4,3], -1 at [4,2]
reward -0.04 for each step
• states
• actions
• rewards
• what is the solution?
Is this a solution?
+1
-1
• only if actions deterministic
• not in this case (actions are stochastic)
• solution/policy
• mapping from each state to an action
Optimal policy
+1
-1
Reward for each step: -2
+1
-1
Reward for each step: -0.1
+1
-1
Reward for each step: -0.04
+1
-1
Reward for each step: -0.01
+1
-1
Reward for each step: +0.01
+1
-1
Markov Decision Process (MDP)
• set of states S, set of actions A, initial state S0 environment
• transition model P(s,a,s’) reward action
• P( [1,1], up, [1,2] ) = 0.8 new state
agent
• reward function r(s)
• r( [4,3] ) = +1
• goal: maximize cumulative reward in the long run
• policy: mapping from S to A
• (s) or (s,a) (deterministic vs. stochastic)
• reinforcement learning
• transitions and rewards usually not available
• how to change the policy based on experience
• how to explore the environment
Computing return from rewards
• episodic (vs. continuing) tasks
• “game over” after N steps
• optimal policy depends on N; harder to analyze
• additive rewards
• V(s0, s1, …) = r(s0) + r(s1) + r(s2) + …
• infinite value for continuing tasks
• discounted rewards
• V(s0, s1, …) = r(s0) + γ*r(s1) + γ2*r(s2) + …
• value bounded if rewards bounded
Value functions
• state value function:
V (s)
• expected return when starting in s and following
• state-action value function: Q(s,a)
• expected return when starting in s, performing a, and
following s
a
• useful for finding the optimal policy r
• can estimate from experience
s’
• pick the best action using Q(s,a)
• Bellman equation
Optimal value functions
• there’s a set of optimal policies
• V defines partial ordering on policies
• they share the same optimal value function
• Bellman optimality equation
s
a
• system of n non-linear equations
• solve for V*(s) r
• easy to extract the optimal policy
s’
• having Q*(s,a) makes it even simpler
Q-learning
• before: on-policy algorithms
• start with a random policy, iteratively improve
• converge to optimal
• Q-learning: off-policy
• use any policy to estimate Q
• Q directly approximates Q* (Bellman optimality eqn)
• independent of the policy being followed
• only requirement: keep updating each (s,a) pair
• Sarsa
Function approximation
• represent Vt as a parameterized function
• linear regression, decision tree, neural net, …
• linear regression:
• update parameters instead of entries in a table
• better generalization
• fewer parameters and updates affect “similar” states as well
• TD update
• treat as one data
x point for regression
y
• want method that can learn on-line (update after each step)
Features
• tile coding, coarse coding
• binary features
• radial basis functions
• typically a Gaussian
• between 0 and 1
[ Sutton & Barto, Reinforcement Learning ]
Splitting and aggregation
• want to discretize the state space
• learn the best discretization during training
• splitting of state space
• start with a single state
• split a state when different parts of that state have different values
• state aggregation
• start with many states
• merge states with similar values
Designing rewards
• robot in a maze
• episodic task, not discounted, +1 when out, 0 for each step
• chess
• GOOD: +1 for winning, -1 losing
• BAD: +0.25 for taking opponent’s pieces
• high reward even when lose
• rewards
• rewards indicate what we want to accomplish
• NOT how we want to accomplish it
• shaping
• positive reward often very “far away”
• rewards for achieving subgoals (domain knowledge)
• also: adjust initial policy or initial value function