# What is the optimal policy and value function?

I am styding reinforcement learning for my machine learning exam. We have a test exam and the image below shows one of the problems.

It would be great if you could give me tips if i did any mistakes solving this exercise or if i have formal issues.

My Solution

By my understanding the reinforcment learning algorithm is getting an reward everytime it goes from state $s_1$ to state $s_2$. The reward in that case is 1 otherwise 0:

$r(s,a) = 1$ if $s = 1$ and $a = right$

$r(s,a) = 0$ if $s = 0,2,3,4$ independent of the action $a$ that the algo takes.

With that reward function i came up with the mapping of states $S$ to actions $A$ with is also called a policy $\pi : S \times A$.

The optimal policy $\pi^*$ is to go as fast as possible to state $s_1$ and then use the $right$ action to get the reward (we are in $s_2$ now). After that it is best to go back to $s_1$ to repeat the process. This is my mapping for $\pi^*$:

$s_0 \rightarrow right$

$s_1 \rightarrow right$

$s_2 \rightarrow left$

$s_3 \rightarrow left$

$s_4 \rightarrow right$

For the value function $V^*(s) = E[\sum_{t=0}^{\infty} \gamma^tr(s_t,\pi^*(s_t)) | s_0 = s]$ i figured out that it would maximize $V$ if the start state is $s_1$ because then the algorithm would generate a reward with the next state by going $right$. Based on the fact that $r(s, a)$ will be 0 for every odd $t$ we could further simplify the formular, but in my opinion that's it.

Can you spot any mistakes in my solution?

Are there any flaws writing down my results?

Thanks for your time.

By my understanding the reinforcment learning algorithm is getting an reward everytime it goes from state $$s_1$$ to state $$s_2$$.

This is correct.

The reward in that case is 1 otherwise 0:

$$r(s,a) = 1$$ if $$s = 1$$ and $$a = right$$

Not quite complete. The reward depends on the successor state only. It does not matter how the state is arrived at. So also, $$r(s,a) = 1$$ if $$s = 3$$ and $$a = left$$.

The optimal policy $$\pi^*$$ is to go as fast as possible to state $$s_1$$ and then use the $$right$$ action to get the reward (we are in $$s_2$$ now). After that it is best to go back to $$s_1$$ to repeat the process.

This is one possible optimal policy. There are two deterministic optimal policies, as it is also valid to go right to $$s_3$$ and back to state $$s_2$$ repeatedly. It is equally valid to go in either direction from $$s_2$$, so any stochastic policy that chooses randomly $$left$$ or $$right$$ when in $$s_2$$ is also optimal.

For the value function $$V^*(s) = E[\sum_{t=0}^{\infty} \gamma^tr(s_t,\pi^*(s_t)) | s_0 = s]$$ i figured out that it would maximize $$V$$ if the start state is $$s_1$$ because then the algorithm would generate a reward with the next state by going $$right$$.

The value function $$V^*(s)$$ should return a value for each state, based on following your optimal policy. So it should be an array of numbers, one for each state. It isn't a choice of "maximal state". The value should be the expected sum of discounted rewards, and your answer should be an array of 5 real values.

To get you started, I calculate that $$V^*(s_0) = 0.66667$$ To completely answer the question, you should calculate $$V^*(s_1)$$ to $$V^*(s_4)$$

You are right that $$V^*(s_1)$$ will be higher, as starting in that state will get an immediate reward of $$1$$ after taking the $$right$$ action.

You should notice that there is some repetition and symmetry in the problem, and that can speed up your calculations for this problem, as it means state values are repeated.

• Your reasoning for $r(s,a)$ makes sense to me. I got confused by the $s_{t+1}$ that caused me to assume that i have to go from a state smaller than 2 to the $s_2$ state, but in fact $t$ is the 'timestamp' not the state indicator. Thanks for pointing out that $V^*(s)$ has be be an array. I assumed that it is the optimal value, however it is the optimal value for each state! I was able to reproduce $V^*(s_0) = \frac{2}{3}$.
– Jens
Aug 10, 2018 at 7:56