7 - Reinforcement Learning

Question 1

4 things RL is built on

Answer 1

• A policy
• A reward
• A value function
• A model of the environemtn

Question 2

Policy

Answer 2

Defines agent’s way of behaving.
Maps from states to probabilities of selecting each action

If agent follows policy π at time t, then π(a|s) is the probability that At=a given St=s

Question 3

Reward signal

Answer 3

Defines the goal

Question 4

Value function

Answer 4

SPecifies what is good in the long term

a state s under policy π denoted vπ(s) is the expected return when starting in s and following π thereafter.

Question 5

Rewards

Answer 5

Immediate desirability of a stateV

Question 6

Values

Answer 6

Long term desirability of a state

Question 7

Model

Answer 7

Predicts or simulates environment.

Model based: similar to planning
Model free RL: trial-and-error

Question 8

Animal Learning

Answer 8

Behaviours that lead to reward reinforced. Behaviours that do not lead to reards are abandoned/reduced

Question 9

Dynamic Programming

Answer 9

Always remember answers to sub problems you solved already

Question 10

Temporal Difference

Answer 10

One stimulus, the secondary reinforcer, predicts arrival of a primary reinforcer.

Eg time.

Question 11

Multi Armed bandit Problems

Answer 11

• Choose among k options
• After each choice, you receive a numerical reward (based on the choice)
• Maximise the reward over some time period (eg 1000 actions)

Question 12

N-armed bandit problem

Each n has an expected reward. call value q

then the value of an action a is the expected reward for a
…. (if we know/don’t know)

Answer 12

If we knew q*(a) (q star subscript not q multiply a) then q(a) is the exptected value of reward Rt given action At
If we don’t then the task is to estimate

Question 13

Greedy actions

Answer 13

Go for the greatest Qt(a).

argmax a Qt(a)

Exploitation

Question 14

Non-Greedy Actions

Answer 14

Choose something else other than max Qt(a).

Exploration

Question 15

Natural way to estimate q(a) by averaging the rewards actually received (Think of sample averages)

Answer 15

Qt(a) = (sum of rewards when a taken prior to t)/(number of times a taken prior to t)

Sample average

Question 16

Near-greedy actions or epsilon-greedy

Answer 16

Behave greedily most of the time but occasionally choose a random action

Question 17

How can we compute the averages Qt(a) efficiently?

This is to do with calculating the on-going estimate, not sum of/times taken

Answer 17

Qn = Qn-1 + (1/n)(Rn - Qn-1)

newEst = oldEst + 1/N[NewSample-OldEst]

Question 18

How can you give more recent rewards more weight in the average?

Answer 18

Use a non-changing step size a (well, alpha)

Qn-1 + a (Rn - Qn-1)

Question 19

Upper confidence bounds

Answer 19

Sample actions that we know little about

At = argmaxa [Qt(a)+c*sqrt(ln(t)/Nt(a))]

Nt(a) here means the number of times a has been selected prior to time t.

c >0 controls degree of exploration

Question 20

Gradient Bandit Algorithms

Answer 20

Learn a preference Ht(a) for each action.

p(At=a) = (e^(Ht(a)))/sum(b=1->k)(e^(Ht(b)))

= PIt(a) (probability of taking action a at time t)

That’s e to the power of Ht(a) divided by the sum of all b from 1 to k where e to the power of Ht(b)

Question 21

Updating action preferences gradient bandit algos (updating Ht+1)

Answer 21

For Ht+1(At) -> Ht(At)+ α(Rt-avgRt)(1-πt(At))
For Ht+1(a) ->Ht(a)- α(Rt-avgRt)πt(a)

First line is for selected action At and second is for a /= At