Skip to content

10 Reinforcement Learning

Clearing up confusing terms from last lecture

\(k\) in value iteration is the number of steps from each value

there are some problems with value iteration

it's very slow \(O(S^2 A)\) time

alternative approach is policy evaluation, and find a policy that converges

policy improvement using one-step look ahead with resulting converged (but not optimal) utilities as future values

  • this is policy iteration!

\(V_{k+1}^{\pi_i} \leftarrow \sum_{s'} T(s, \pi_i(s), s')\) [R... finish this]

  • both value iteration and policy iteration compute the same thing (all optimal values)
  • in value iteration
  • every iteration updates both the values and (implicitly)

for mdp algos, you want to compute optimal values, either using value or policy iteration

turning values into a policy: policy extraction

Define these 4 in simple terms

  • value iteration
  • policy iteration
  • policy evaluation
  • policy extraction

NOW REINFORCEMENT LEARNING

Double Bandit

  • toggle this slot machine
  • first: ik I will get 1$ every time
  • second: 75% 2$ 25% 0$
  • would pick the second machine, the expected value is greater in the long run.
  • solving the mdp is offline planning, you can compute all the values, which slot machine is better for you
  • let's say we do not have any of the probabilities? we can determine by playing the game

for an episode - red machine: 2 dollars - red: 2$ - red: 0 - red: 2 - red: 0 - ...

we can learn the essence of the game through experience, what the probability values are going to be

another game - r: 0 - r: 0 - r: 2 - r: 2 - r: 2 - r: 0 - r: 2 - ...

what was missing in our mdp?

  • states, actions, rewards, transition functions
  • so how do we figure out the transition function
  • and how do I figure out the rewards?

so there's a lot of stuff to figure out rather than having up front

important ideas

  • exploration: try unknown actions
  • exploitation: have to use what you know
  • regret: even when you learn, you can make mistakes
  • sampling: because of chance you have to try things differently
  • Difficulty

Reinforcement Learning: How does it work

env: state space

mdp is non-deterministic

goal is to act in a way that maximizes rewards

in RL this is different because we don't know what states are "good" until we visit them

Have to focus on the learning aspect, goes back to the way humans learn, and behavioural learning. You have to learn through experience

The agent is going to a state, it's going to learn the space, and learn the probability of the space.

sometimes I'm going to take actions and they're going to succeed, and sometimes I'm going to take actions and they're not going to succeed.

offline (MDPs) can compute the solution

online (reinforcement learning) have to discover the solution

Model Based Learning

  • if I know the MDP I can solve it with all the techniques we already learned
  • but if we don't know the mdp we can learn an empirical MDP
  • count outcomes \(s'\) for each \(s, a\)
  • Normalized to give an estimate of \(T(s, a, s')\)
  • discover each \(R(s, a, s')\) when we experience \((s, a, s')\)
  • Solve the learned MDP
  • for example, use value iteration, as before

assume that when we move through the environment,

we still get a noisy estimate, when we get that information, we believe that is the correct information.

Example: Model Based Learning

policy - B -> C - E -> C - C -> D

episode 1 - B, East, C, -1 - C, East, D, -1 - D, exit, x, +10

episode 2 - B, east, C, -1 - C, east, D, -1 - D, exit, x, +10

episode 3 - E, north, C, -1 - C, east, D, -1 - D, exit, x, +10

episode 4 - E, north, C, -1 - C, east, A, -1 - A, exit, x, -10

assume \(\gamma = 1\)

let's calculate

Let's do another RL problem here

compute the expected age of cs188 students

known \(P(A)\) \(E[A] = \sum_a P(a) \cdot a\)

equivalent to solving an MDP

The model to figure out the expected age

figure out the distribution of ages

without \(P(a)\) instead collect samples \([a_1, a_2, a_3, ...]\)

unknown \(P(a)\): "model based" \(\hat{P}(a) = \text{num}(a)/N\) \(E[A] \approx \sum_a \hat{P}(a) \cdot a\)

calculates an average, requires calculating probability

Why does this work? Because eventually you learn the right model

unknown \(P(a)\): "model free" \(E[A] = \frac{1}{N} \sum_i a_i\)

continue to update my average, will eventually converge, don't need the probability

implicitly defining the probability in the average.

in expectation these two values will be exactly the same

we don't need a model to compute the avgs

MODEL FREE LEARNING

Passive reinforcement learning

  • if I want the best restaurant, I'll try all the restaurants until I know what's the best one
  • we won't do this

if we weren't doing passive, we would ask:

how do we figure out how much to try vs how much to exploit?

Passive

  • simplified task: policy evaluation
  • input: fixed policy
  • don't know transition
  • don't know rewards
  • goal: learn the state values
  • In this case
  • learner is "along for the ride"
  • no choice about what actions to take
  • just execute and learn from experience
  • this is NOT offline planning! you actually take actions in this world

Direct evaluation

  • goal: compute values for each state under \(\pi\)
  • idea: average together observed sample values
  • act according to \(\pi\)
  • every time you visit a state, write down what the sum of discounted rewards turned out to be
  • average those samples
  • this is called direct evaluation

so from the example above

if we observed episodes 1 and 2, if we wanted the value of B it would be the sum of rewards, #=: -1 + -1 + 10

following the same logic:

D has a value of 10

C has a value of 9

if we observe all of ep 1-4

what is the value of A? -10

what is the value of B? still +8

what is the value of C? 4 times in C, #=: (9 + 9 + 9 + -11) / 4

and D is still 10

(C, East) is the policy, and what we know is that 75% of the episodes we went to D and 25% we went to A

  • what's good about direct evaluation?
  • easy to understand
  • doesn't require any knowledge of \(T\) or \(R\)
  • eventually computes the correct average values
  • using the sample transitions
  • what's bad about it
  • wastes information about state connections
  • each state must be learned separately
  • so, it takes a long time to learn (B and E are the same and we don't use that symmetry there at any point, if B and E have the same policy, why are their values different)
  • maybe we can take advantage in the future?

why are we doing direct evaluation

trying to compute \(V^{\pi}(s)\)

simplified bellman updates calculate \(V\) for a fixed policy: each found, replace \(V\) with a one-step-look-ahead, layer over \(V\)

\(V^{\pi}_0(s) = 0\) \(V^{\pi}_{k+1}(s) \leftarrow \sum_{s'}\) ... finish this

utility of ending up in \(s'\) if you take action \(\pi(s)\) in state \(s\)

  • this approach is fully exploited the connections between the states, but we need \(T\) and \(R\) to do it!
  • how can we do this to update \(V\) without knowing \(T\) and \(R\)?
  • in other words, how do we take a weighted average without knowing the weights?

we need to take the concept of running averages, take an average based on the samples. We don't have access to a transition function and reward function

let's try to figure that out

we have this policy eval

we want to take samples of outcomes. and then average.