Reinforcement Learning 第七周课程笔记

• This week’s tasks
• Why changing RF?
• How to change RF without changing optimal policy.
  • 1. Multiply by a positive constant
  • 2. shift by a constant
  • 3. nonlinear potential-based reward shaping
• Q-learning with potential
• What have we learned?

This week’s tasks

• watch Reward Shaping.
• read Ng, Harada, Russell (1999) and Asmuth, Littman, Zinkov (2008).
• office hours on Friday, October 2nd, from 4-5 pm(EST).
• Homework 6.

Why changing RF?

Given an MDP, RF can affect the behavior of the learner/agent so it ultimately specifies the behavior (or policy) we want for the MDP. So changing rewards can make the MDP easy to solve and represent

1. Semantics: what the agent are expected to do at each state;
2. Efficiency: speed (experience and/or computation needed), space (complexity), and solvability .

How to change RF without changing optimal policy.

Given an MDP described by <S, A, R, T, γ>, there are three ways to change R without changing optimal solution. (Note, if we know T, then it is not a RL problem any more, so this part of lecture if for MDP not RL specifically).

1. Multiply by a positive constant ( non-zero ‘cause multiply by 0 will erase all the reward information)
2. shift by a constant
3. non-linear potential-based

1. Multiply by a positive constant

• Q(s,a) is the solution of Bellman function with the old RF R(s,a).
• R’(s,a) is a new RF with is the old RF multiplying by a constant.
• What’s the new solution Q’(s,a) with respect to the new RF R’(s,a) and old Q(s,a)?

Here is how to solve the problem:

1. Q = R + γR+γ²R + … + γ^∞ R)
2. Q’ = R’ + γR’+γ²R’ + … + γ^∞ R’
3. Replace R’ with c*R, Q’=(c*R) +γ(c*R)+γ²(c*R) + … + γ^∞ (c*R) =c(R + γR+γ²R + … + γ^∞ R) =c*Q

2. shift by a constant

1. Q = R + γR+γ²R + … + γ^∞ R)
2. Q’ = R’ + γR’+γ²R’ + … + γ^∞ R’
3. Replace R’ with R+c, Q’=(R+c) +γ(R+c)+γ²(R+c) + … + γ^∞ (R+c) =(R + γR+γ²R + … + γ^∞ R) + (c+γc+γ²c + … + γ^∞ c)
4. The first part is Q and the second part is geometric series. So, Q’ = Q + c/(1-γ)

3. nonlinear potential-based reward shaping

1. Q = R + γR+γ²R + … + γ^∞ R)
2. Q’ = R’ + γR’+γ²R’ + … + γ^∞ R’
3. Replace R’ with R-ψ(s) + γψ(s’), Q’=(R-ψ(s) + γψ(s’)) +γ(R-ψ(s’) + γψ(s’’))+γ²(R-ψ(s’’) + γψ(s’’’)) + … + γ^∞ (R-ψ(s^∞ ) + γψ(s’^∞ )) =(R + γR+γ²R + … + γ^∞ R) + (-ψ(s) + γψ(s’) +γ(-ψ(s’) + γψ(s’’))+γ²(-ψ(‘’s) + γψ(s’’’)) + … + γ^∞ (-ψ(s^∞ ) + γψ(s’^∞ ))
4. The first part is Q. In the second part, most of the elements are cancelling each other out and only has the very first and last elements left. So, Q’ = Q + (-ψ(s) + γ^∞ ψ(s’^∞ )
5. Given γ is in (0,1), so γ^∞ =0. Then we have Q’: Q’ = Q - ψ(s)

Q-learning with potential

Updating the Q function with the potential based reward shaping,

1. Q function will converge at Q*(s,a).
2. we know that Q(s,a) = Q*(s,a) - ψ(s). If we initialize Q(s,a) with zero, then Q*(s,a) - ψ(s) = Q*(s,a) - max_aQ*(s,a) = 0, that means a is optimal.
3. so Q-learning with potential is like initializing Q at Q*

What have we learned?

• Potential functions is a way to speed up the process to solve MDP
• Reward shaping might have suboptimal positive loops which will never converge?

2015-09-29 初稿
2015-12-04 reviewed and revised