Week 9: Adding a 'World Model' (Only a Brief Outlook)

Question 1

RL is often introduced as an

Answer 1

Markov-Decision Process (MP)

Question 2

MDP is (2)

Answer 2

a succession of states (e.g. positions on a chess board), in each state the agent chooses and action (leading to a new state), and in each state has an associated immediate reward (can also be zero reward).

State transitions/action choices can be probabilistic.

Question 3

MDP If S is set of states called

Answer 3

state space

Question 4

MDP A is set of actions called

Answer 4

action space

Question 5

MDP Policy:

Answer 5

mapping from states to actions (e.g., given state Si, I choose action j)

Question 6

The goal of MDP process is to

Answer 6

find a good “policy” for the decision maker

Question 7

At start of RL we don’t know the best policy or the

Answer 7

value function as agent with default policy, performs action, something changes in enviroment and gives rewars and update state

Question 8

Set up of model-free RL:

Answer 8

as agent with default policy, performs action, something changes in enviroment and potentially gives reward and update state

Question 9

As compared to model-free RL, model-based RL

Answer 9

we assume we know how the enviroment works

Question 10

Model-based RL: we assume we know how the enviroment works,

In other words … (2)

Answer 10

given state s and action a there is some (known) probability that I will transition to the state s’ (another state)

This is the ‘probability model’ or ‘world model (i.e., rules of chess dicate the next possible states)

Question 11

Since in model-based RL we have proability of state transitions we can

Answer 11

estimate the probability of future reward in state s’

Question 12

S’

Answer 12

State prime (next state)

Question 13

The goal after finding we estimate the probability of future reward in next state since model-based RL have proabilities of state transitions

(2)

Answer 13

1. Learn an optimal policy (best choice in each state)
2. Learn an optimal value function (correctly attributing rewards to state

Question 14

The problem to goal - (2)

Answer 14

• Take chess, we can not compute all board positions and simply calculate V and P

Question 15

The solution to problem

Answer 15

Do it iteratively, looking a few steps ahead

Question 16

Using formula of V we change this slightly to (achieve the goal) - (4)

Answer 16

use policy that indicates max reward

separate ro (current reward) from rest

Write equation as recursive form

This is called as Bellman’s equatoion

Question 17

Formula of V (used to change into Bellman’s equation) is (2)

Answer 17

sum of expected future reward for each possible state by adding up the sum of discounted future reward + current reward (given state s0, i.e., now)

Formula taken from model-free RL

Question 18

What does it mean of writing expected reinforcement equation given state now as written recursive form (as Bellman’s equation) - (4)

Answer 18

If the value function we are trying to optimize is a recursive version of itself we can break up the problem into smaller individual problems.

Thus, Optimize locally then put things together. It can be shown that global solution is then still optimal.

Also, since the optimal policy is the one that maximizes reward, that means if we have a value function => decision making becomes easy, i.e., we can extract policy: we just pick the action that maximizes V

Similarly, if we have the policy we can create the value function (by picking the next state according to the policy)

Question 19

We build up V and P in formula of

So if we know rules of game or don’t know optimal policy or value function then

Answer 19

Iteratively build the optimal policy and value function (solution)

Question 20

We can build the optimal policy and value function - (2)

Answer 20

One way is (somewhat reminiscent of our Q-learning football-kicking robot) to start with a small problem, then work your way back (local -> global) , the robot example, only after we learned to kick the ball when in the field with the ball, could we then in the next learning episode learn to walk into the field with the ball

Simialrly, start with a winning case, then optimise the step before, building up the value function recursively (value iteration)

Question 21

Two algorithms to solve the problem of building V and P

Answer 21

value iteration and policy iteration

Question 22

Value iteration is where we

Answer 22

iteratively (episode by peisode) update V for state we go through (a lot like the football robot)

Question 23

We can think for V for value iteration as

Answer 23

one large table with entires for all possible states (initalised e.g. with 0)

Question 24

V iteration is different from Q-learning as

Answer 24

we know the probabilities of state transitions P, we can evaluate (1) for all possible actions (with our initial V).

Pick the best action and update current estimate of V (that is V(s)). => perform state transition and repeat the process. And so onwards …

Once you have a good estimate of V: you can extract the optimal policy as the policy that maximises reward

Compare to football-robot , it took actions at random

Question 25

These formula same

Answer 25

Both the same

Bellman’s equation with state transitions probabilities P with it (2)

Question 26

Policy iteration (5)

Answer 26

Rather than finding the action that maximizes V, we lock in a policy at start (our best estimate)

Then we build up V.

Then iterate through alternative actions to refine the action choice (policy)

Then lock in the updated policy, and do another value iteration …

This can be faster (in the computer) than value iteration