2
$\begingroup$

I am having trouble understanding the following problem and Q learning in general.

What I know so far about Q learning is that Q-learning is a model free method, i.e., it doesn’t need to learn P(s’|s,a). Thus it can compare the expected utility of the available actions without the model of the environment.It will also eventually find a policy that is the maximum achievable. However, I am not able to use this knowledge to do this problem. The answer is given in red.

enter image description here

If we are to look at time t = 1, then the equation becomes the following: $$ Q_{t+1}(s,a)=(1-1/2)(1)+1/2[R(s,a,s^{'})+(1) max⁡Q(s^{'},a^{'})] $$ How do I proceed from here?

$\endgroup$
1
$\begingroup$

At t=1, you just took action a = d at state s = S and ended in s' = S again with 0 reward. So:

$Q(S,d) = (1 - 1/2)(1) + 1/2[0 + (1)(1)] = 1$ ($maxQ(s',a')$ is the maximum value you can get from state S in this case, which is 1)

So nothing changes. At t=2, it is exactly the same as t=1, so nothing changes again.

At t=3, we just took action p at s = S and ended on state s' = P with reward +1. Thus:

$Q(S,p) = (1 - 1/2)(0) + 1/2[1 + (1)(1)] = 1$ ($maxQ(s',a')$ here refers to $maxQ(P,a')$, the maximum value we can get from state P, which is 1.

So, update $Q(S,p)$ to 1.

At t=4, we just took action a = p at state s = P, ending in state s' = S with reward 0. Thus:

$Q(P,p) = (1 - 1/2)(0) + 1/2[0 + (1)(1)] = 1/2$

So, update $Q(P,p)$ to 1/2.

I think you can do t=5 and t=6 by yourself now, just note that maxQ at a terminal state is 0 (because there is no future reward to accumulate). If you can't, just tell me and I'll update the answer.

$\endgroup$
  • $\begingroup$ I had a few questions regarding this. In the equation, you're plugging in 1 for maxQ(s',a'). Does this refer to previous Q(s,a)? Or where exactly is this one coming from? And, if we took action p at t = 3, then why do we still update Q(S,d) to 1 also? $\endgroup$ – Jonathan Jun 9 '16 at 16:02
  • 1
    $\begingroup$ At t=1 we end in S, so you look at the table for all values with state S. We have S,d = 1 and S,p = 0 (from t=0), so we pick 1. As for your last question, I'm not sure what you're referring to, since S,d is not updated, it keeps its value as 1 since the beginning. $\endgroup$ – rcpinto Jun 9 '16 at 17:32
  • $\begingroup$ For t=6, the equation I got was Q(P,d) = (1/2)(1)+(1/2)[4+1] = 1/2 + 5/2 = 3. However, the answer is 5/2. what am i doing wrong here? $\endgroup$ – Jonathan Jun 10 '16 at 6:42
  • 1
    $\begingroup$ "just note that maxQ at a terminal state is 0" :) $\endgroup$ – rcpinto Jun 10 '16 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.