Reinforcement Learning Notes

---

The basic algorithm of the agent:

do forever
  observe x
  suggest a according to some decision-algorithm
  execute a
  observe y
  receive reward r(y) or r(x,y)
  modify decision-algorithm
  repeat

a can be "no-op".
r can be 0 every step when nothing happens.

Sample definitions of x:

• Clocksin and Moore
• House Robot
• Ant World
• Tyrrell's world

• Chess board
  • x = (x1,x2,..,x64) where each x_i = what?
  • or x = (x1,x2,..,x32) where each x_i = what?

---

Probabilistic Transitions

Start in state x:

In state x,
taking action b gives a guaranteed reward of 1.5.
Taking action a normally leads to a reward of only 1, but sometimes leads to a reward of 5.

P_xa(y) = 0.8
P_xa(z) = 0.2
P_xa(w) = 0 for all w other than y,z
(probabilistic transition)

P_xb(s) = 1
P_xb(w) = 0 for all w other than s
(deterministic transition)

---

Non-Markovian worlds

x = ( direction )
Consider:
P ( x_t+1=bump   |   x_t=s_t,   a_t=b_t,   x_t-1=s_t-1,   a_t-1=b_t-1,   ... )

P ( bump | wall is N, move N, wall is N, move N, wall is N, move N )
is higher than:
P ( bump | wall is N, move N, wall not visible, move N, wall not visible, move N )

i.e. There isn't simply a constant:
P ( bump | wall is N, move N )

Q. What simple change would turn the above into a MDP (in fact, a deterministic MDP)?

Consider:

1. Deterministic world that looks deterministic.
2. Deterministic world that looks probabilistic.

3. Probabilistic world that looks probabilistic.
4. Probabilistic world that looks deterministic.

• Kaelbling survey
  • non-Markov worlds

• Examples:
  • Chess - Apparently deterministic - given x, take a, see predictable next state y. However, y is the state your opponent gets to take an action in, not you. He takes unpredictable action b, leading to state z. So from your point of view, you see x, take a, wait for a bit, and then see unpredictable z. From your point of view, world is probabilistic (as is any world with an opponent).
  • Football - Non-Markov world. Don't know what's in other players' minds, so don't know if set-piece free kick will work this time (as it did last time).

• All adversarial games (chess, Xs and Os):

  Observe x
  Take a
  (Opponent makes non-deterministic move)
  Observe y
  

• Can non-Markov worlds be solved?
  • Some can - e.g. Transition depends on this state plus previous state only.
  • Some can't - e.g. World where transition probabilities change randomly. Consequences of all actions are random.

• Is the universe deterministic?
  • Determinism
    • Determinism, quantum mechanics and classical physics
  • Scientific determinism
  • Interpretation of quantum mechanics
  • Quantum indeterminacy
  • Hidden variable theory - The (very much minority) theory that the universe could be deterministic below the quantum level, but appear probabilistic at the quantum level.

---

2.1.3 - Expected Reward

In the above, How do we decide which action to take?
Look at expected reward:
E_a(r) = 0.2 (5) + 0.8 (1)
          = 1.8
E_b(r) = 1 (1.5)
          = 1.5
Action a is better.

What do the probabilities mean?
They mean that if you take a 100 times, you expect 20 5's and 80 1's. Total reward 180.
If you take b 100 times you expect 100 1.5's. Total reward 150.

Maximise E(r).

r_min ≤ E(r) ≤ r_max

If all rewards between r_min and r_max
E(r) = p₁ r₁ + ... + p_n r_n
≥ p₁ r_min + ... + p_n r_min
= 1 . r_min

---

E(r) exists, E(y) doesn't exist

Imagine a state definition for a robot carrying blocks to put in a bin:
x = (x1,x2)
x1 = what you are carrying: 0=not carrying block, 1=carrying block
x2 = direction of bin, values 0-9

You are in state x = (1,5).
Imagine that if you take some action a, you go to state y with probabilities:

y               Pxa(y)          reward

(1,8)           0.4             10
(0,8)           0.3             5
(1,5)           0.2             1
(0,5)           0.1             0

You can calculate E(r).
Q. What is it?

But "E(y)" is meaningless.
Consider the sum of the y's times their probabilities
= (1,8) 0.4 + (0,8) 0.3 + (1,5) 0.2 + (0,5) 0.1
= (0.6, 7.1)

You are never in this state when you take a.
In fact, this state doesn't exist.
"0.6" doesn't have a meaning.
The state space is not a continuous space. It is a discrete space of points.

---

r(x,y)

Typically, we don't reward for the correct action, r = r(x,a):

in state x
if took action b
  then reward 1
else
  reward 0

because we don't know the correct action!
Instead we reward on getting to some state (somehow, we don't know how), r = r(x,y):

in state x
if got to state z
  then reward 1
else
  reward 0

---

e.g. In the following:

Taking action a in state x,
P(r=5) = 0.2
P(r=0) = 0.4
P(r=3) = 0.3 + 0.1
          = 0.4
Question - What is E(r)?

---

Reward on Continuous or Transition?

Reward on transition to good state only: r = r(x,y).
e.g. x = not at waterhole, y = at waterhole. Problem - may leave state to come back in! See Discussion.

Reward for arriving and staying in good state: r = r(y).

---

2.1.4 Deterministic v. Stochastic Policy

a       a1   a2    a3
Q(x,a)  0    5.1   5

Deterministic policy - When in x, always take action a2.

Stochastic policy - When in x, 80 % of time take a2, 20 % of time take a3.

Typically - Start stochastic. Become more deterministic as we learn.

---

Short-term loss for Long-term gain

Not just maximise immediate E(r) (i.e. deal with probability).

Maximise long-term sum of expected rewards. This may involve taking a short-term loss for long-term gain (equivalent to allowing a move downhill in hill-climbing).

Discounted Reward

0 ≤ γ < 1

(e.g. γ = 0.9)

If rewards can be positive or negative, R may be a sum of positive and negative terms.

Special case: γ = 0
Doesn't work: γ = 1 (see later)

The interesting situation is in the middle (0 < γ < 1)

Short-term loss for Long-term gain

r in the future can even override immediate punishment

If we decide what to do based on which path has highest R, then [punishment now, r in the future] can beat [reward now, but not in future] if:

1. r is big enough
2. r is near enough - not discounted by γⁿ
3. both of the above

---

Bounds

If maximum reward is r_max, what is maximum possible value of R?
The most it could be would be to get the maximum reward every step:


What is this quantity on the right? Let:

Multiply by γ:

Subtract the 2 equations:

And we get a value for X:

That is:

See Appendix A and Appendix B.

This is just the Negative Binomial Series in the Binomial Theorem.
(x+1)^(-1) = 1 - x + x² - x³ + x⁴ - ...
Let x = - γ

---

Exercise

---

2.1.5 DP

Note in DP if γ = 0 (only look at immediate reward) you only need one iteration of updates and you are done.
You have worked out immediate E(r) completely.

---

2.1.5 How do I return to state x?

In the real world, we may not know how to get back to state x to try another action:
x = "I am at party"
a = "I say chat-up line c₁"
result - punishment

I might want to say "Go back to x, try c₂" but I may not know how to get back to x. All I can do is try out actions in the states in which I happen to find myself. I have to wait until state x happens to present itself again.

Q-learning can work even when states and actions are experienced haphazardly.

---

2.1.5 - DP and Q-learning

Q-learning is for when you don't know P_xa(y) and P_xa(r).

But one approach is just:
Interact with world large number of times to build up a table of estimates for P_xa(y) and P_xa(r).
Then just do offline DP.

---

2.1.5 Q-learning

We keep Q-values Q(x,a) for each (x,a) pair.
We tend to take the action with the highest Q-value:

max_b Q(x,b)

The Q-value will express the discounted reward above:

Can be built up recursively:

---

Sampling

Using this update rule:

the Q-value will bounce back and forth:

Q(x,a) := 5
Q(x,a) := 10
Q(x,a) := 6
...

More sensible to build up an average:

Q(x,a) := 5
Q(x,a) := 1/2 (5 + 10)
Q(x,a) := 1/3 (5 + 10 + 6)
...

See Appendix A for how to build up a running average like this without needing infinite memory.

In general, we use the Notation of updating the running average D "in the direction of" the latest sample d, rather than assigning directly to it:

If   d < D   then the running average D goes down. If   d > D   then the running average D goes up.

So the Q-value is updated in the direction of the current sample:

---

D is bounded

Theorem B.1 - If d bounded, then D bounded.

α must start at 1 to get rid of D_init

Thereafter α can be anything from 0 to 1.

• However, α cannot be outside those bounds.
  e.g. α starts at 1, thereafter α = 11.
  Then let's say we get any non-zero sample d once, then 0 forever. i.e. Samples d, 0, 0, ....
  Then D is not bounded. It goes:

  D := 0 + 1.d     (since α starts at 1)
  D := -10 d + 0
  D := -10 (-10 d) + 0
  D := - 10³ d
  D := 10⁴ d
  D := - 10⁵ d
  ....
  D not bounded

---

Q is bounded

Theorem B.2

i.e. If take this action, you will get immediate reward r_max
and you can get next reward r_max (it is the best you can get in next state, other actions may be worse)
and you can get next reward r_max ..
....

i.e. If take this action, you will get immediate reward r_min
and you have to get next reward r_min (all actions in next state lead to the worst reward r_min, otherwise the Q-value would be higher)
and you have to get next reward r_min ..
....

i.e. You are trapped in an attractor from which you cannot escape.
You cannot ever again get out and go to a state with rewards greater than r_min (and such states must exist).
Not necessarily a single absorbing state, but a family of states outside of which you can never leave.

---

Note if expected reward E(r) = r_min, then you will definitely get r_min on this action (r deterministic, though y can still be probabilistic).
If any reward r   >   r_min has non-zero probability, then E(r)   >   r_min

E(r) = p r_min + (1-p) r
> p r_min + (1-p) r_min
= r_min

---

How Q-learning works

---

Building a world model

---

Convergence

---

The control policy

---

Appendix A

Theorem A.2

If start at:   α = 1/t   then initial Q-values bias our Q-values for some time.
And since we only run for finite time in any finite experiment, the bias may still be there after learning.

Consider being "born" with Q-values already filled in (i.e. in DNA) and then start learning:

• Lamarckism:
  • Lamarck
  • Lamarckian inheritance (and here) - doesn't happen in nature, but could happen in machines.

• Not-quite Lamarckism: The Baldwin Effect
  • Baldwin
  • The Baldwin Effect (and here) - Evolution and learning can look like Lamarckian inheritance. We don't have infinite time to learn. It's easier to learn the optimal policy in your finite lifespan if you are born close to it to begin with.
  • The original paper: "A New Factor in Evolution", James Mark Baldwin, American Naturalist, 1896.

• Example of being "born" with Q-values:
  x = at cliff edge
  a1 = go forward
  a2 = go back
  bad Q-values to be born with:

           a1      a2
  Q(x,a)   0       0
  

  good Q-values to be born with:

           a1        a2
  Q(x,a)   -1000     0
  

  - even if experiment in childhood, with a moderate temperature Boltzmann control policy, still unlikely to try a1.

• Other examples of not-quite Lamarckism:
  • Gunnar Kaati's work on diet affecting genes in the next two generations. (Possibly choosing from pre-selected pool, turning genes for famine/plenty on and off.)

  • It is long established that pregnant mother's lifestyle influences development of fetus.
    Mother's diet, stress, alcohol, influence baby's development. (And genes?)

  • Robert Pruitt's work on plants being able to reconstruct genes from their ancestors that they strictly speaking did not inherit from their parents. i.e. Plant considers its own DNA unsatisfactory, and changes it.

  • Epigenetics
  • Epigenetics: Genome, Meet Your Environment by Leslie A. Pray - "As the evidence accumulates for epigenetics, researchers reacquire a taste for Lamarckism"