# Sutton and Barto 2nd Edition Exercise 13.1

I'm attempting exercise 13.1 in the Sutton and Barto textbook. It asks for an optimal probability for selecting action right in the short corridor scenario (see first 6 lines of the image below for the scenario).

Exercise 13.1: Use your knowledge of the gridworld and its dynamics to determine an exact symbolic expression for the optimal probability of selecting the right action in Example 13.1.

My attempt: Letting $$p$$ denote the probability of choosing right, I understand that using the Bellman equations, we can solve for the value of $$s_1, s_2, s_3$$ where the states are numbered from left to right in terms of $$p$$. We have $$v(s_1) = \frac{2-p}{p-1}$$, $$v(s_2) = \frac{1}{(p-1)p}$$, $$v(s_3) = -\frac{p+1}{p}$$. I can see how we can find the max of each of these functions to get the best optimal policy, given the state we're currently in.

However, how do you find the optimal policy generally (irrespective of starting state)? I found solutions here, which magically arrives at $$\frac{p^2-2p+2}{p(1-p)}$$. Can someone explain this part?

https://github.com/brynhayder/reinforcement_learning_an_introduction/blob/master/exercises/exercises.pdf • The expression $(p^2-2p+2)/(p(1-p))$ is positive for all, so I wouldn't rely on it... May 24, 2021 at 9:24

There are problems with both the approach and the expressions that you have. I don't want to just give the correct solution, though, that's an exercise for you to go through and learn from your own experience trying to accomplish it. Instead, let me illustrate that your expressions for $$v(s_i)$$ are wrong. To do that we'll just do a Monte-Carlo estimate for a range of values of $$p$$ and compare to your expression.

Here's the Python code that runs a single payout starting from state state and following the policy with probability p of choosing "right". It returns the collected reward:

import numpy as np

def playout(state, p):
reward = 0
while state != 0:
action_right = np.random.rand() < p
move_right = action_right if state != 2 else (not action_right)
state = state - 1 if move_right else state + 1
state = 3 if state > 3 else state
reward -= 1
return reward


Then we make a simulation code that runs the playout multiple times, collects the reward counts, and returns the average reward (so, essentially estimates $$v^\pi(s_i)$$):

from collections import defaultdict

def simulate(state, p, n):
rewards = defaultdict(lambda : 0, {})
for _ in range(n):
rewards[playout(state,p)] += 1
results = np.array([[a,b] for a,b in rewards.items()]).T
reward , nplayouts = results , results
value = (reward * nplayouts).sum() / nplayouts.sum()
return value


Finally, I make a grid in p and run each playout 10000 times:

p = np.linspace(0,1,51)[1:-1]
v3 = [simulate(3,p,10000) for p in p]
v2 = [simulate(2,p,10000) for p in p]
v1 = [simulate(1,p,10000) for p in p]


I've plotted the resulting value estimates for each state. Together with your expression for them (blue curves). And the correct expression (red curve) that I've obtained by actually writing down and solving the equations: As you can see, the expressions you've presented are all too far off from the results that the simulation returns. More than that - the asymptotic behavior of your solutions at $$p\to0$$ and $$p\to1$$ doesn't make much sense.

I've obtained the expressions for the red curves above by solving the system for $$v(s_i)$$ on my own account - without relying on weird and wrong solutions that I googled on the internet. Which I'd recommend you do as well.

Finally, the question of the exercise is to find an optimal $$p$$ for a policy that starts at $$s_3$$ - not "irrespective of starting state" as you've thought is should be. Unlike your expression the correct expression for $$v(s_3)$$ has a maximum, which can be found analytically and it is $$\max_p v(s_3) = -6-4\sqrt2 \simeq -11.6$$ $$\text{at}\quad p = ??? \simeq 0.59$$

• I reread the question, it is word for word what I wrote in the question, where does it say to find an optimal policy that starts at state $s_3$? May 25, 2021 at 19:39
• @Snowball "S" and "G" is a standard notation for start and end states across the book. See e.g. examples 6.5, 6.6, 8.1 May 25, 2021 at 20:14

Here is a simple way to solve the problem.
With probability p of moving right in normal grids, we can write down the transition matrix.

$$Q=\begin{bmatrix} 1-p & p & 0 \\ p & 0 & 1-p \\ 0 & 1-p & 0 \end{bmatrix}$$

From this answer we have the method to calculate the expected steps between two states. https://math.stackexchange.com/questions/691494/expected-number-of-steps-between-states-in-a-markov-chain

which is, the sum of the first row of the matrix $$(I-Q)^{-1}$$

$$M=(I-Q)^{-1}=\begin{bmatrix} \frac{2}{p}+\frac{1}{1-p} & \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p} \\ \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p}+\frac{1}{1-p} & \frac{1}{p} \\ \frac{1}{p} & \frac{1}{p} & \frac{1}{p} \end{bmatrix}$$ So the expectation of the number of steps is

$$E[t]=\frac{4}{p}+\frac{2}{1-p}$$

And since the reward is -1 per step $$J(p)=-E[t]=-\frac{4}{p}-\frac{2}{1-p}$$

$$\frac{dJ}{dp}=\frac{4}{p^2}-\frac{2}{(1-p)^2}=0$$ $$2p^2=4(1-p)^2$$ $$p^2-4p+2=0$$

We then have solutions $$p=2\pm\sqrt{2}$$, and since $$p$$ is a probability in $$[0,1]$$ $$\hat{p} = 2-\sqrt{2} \approx 0.586$$