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 Answer 1

0
$\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$
4
  • $\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$
    – user40759
    Jun 9, 2016 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, 2016 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$
    – user40759
    Jun 10, 2016 at 6:42
  • 1
    $\begingroup$ "just note that maxQ at a terminal state is 0" :) $\endgroup$
    – rcpinto
    Jun 10, 2016 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.