Skip to main content
added 635 characters in body
Source Link
David
  • 5k
  • 1
  • 9
  • 31

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.

I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.

Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.

'Left Policy'

\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$

'Right Policy'

\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$

As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.

It is important to note that if we take the 'left' action in state $s_0$ then our policy would never take us to state $s_R$, and the same for the right action and state $s_L$, however due to the definition of an optimal policy requiring $v_{\pi ^*}(s) \geq v_{\pi}(s)\; \forall s \in \mathcal{S}$ then we must evaluate the value function for all states, even ones that would not be visited under a policy you are evaluating. This means that the state for $s_R$ will change whether we go right or left, because the value of this state depends on the value of $s_0$, which clearly changes depending on whether we go right or left.

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.

I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.

Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.

'Left Policy'

\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$

'Right Policy'

\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$

As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.

I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.

Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.

'Left Policy'

\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$

'Right Policy'

\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$

As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.

It is important to note that if we take the 'left' action in state $s_0$ then our policy would never take us to state $s_R$, and the same for the right action and state $s_L$, however due to the definition of an optimal policy requiring $v_{\pi ^*}(s) \geq v_{\pi}(s)\; \forall s \in \mathcal{S}$ then we must evaluate the value function for all states, even ones that would not be visited under a policy you are evaluating. This means that the state for $s_R$ will change whether we go right or left, because the value of this state depends on the value of $s_0$, which clearly changes depending on whether we go right or left.

Source Link
David
  • 5k
  • 1
  • 9
  • 31

Your answer is correct but I am not sure exactly on how you arrived at it, as e.g. in the last case you don't know that $v_{L,n}(S_0) = v_{R,n}(S_0)$.

I will show for case B when $\gamma = 0.9$ as case A is trivial and hopefully you can apply what I've done in case B to case C so that you get exact answers.

Now, as you stated $v(s) = \mathbb{E}[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$. Assuming that $\gamma = 0.9$ we can calculate the values for each state under the policy of taking the left action. Note that because we are looking for deterministic policies and the environment is deterministic then a lot of the expectations can be disregarded as nothing random is happening.

'Left Policy'

\begin{align}v(s_0) &= 1 + 0.9 \times v(s_L) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can solve this set of linear equations to get $v(s_0) = \frac{100}{19}, v(s_L) = \frac{90}{19}, v(s_R) = \frac{128}{19}\;.$

'Right Policy'

\begin{align}v(s_0) &= 0 + 0.9 \times v(s_R) \\ v(s_L) &= 0 + 0.9 \times v(s_0) \\ v(s_R) &= 2 + 0.9 \times v(s_0) \end{align} We can again solve these to obtain $v(s_0) = \frac{180}{19}, v(s_L) = \frac{162}{19}, v(s_R) = \frac{200}{19}\;.$

As we can see, for each of the states the value function is larger for all of the states under the policy 'go right', thus this is the optimal policy for the case of $\gamma = 0.9$.