Sutton and Barto 2nd Edition Exercise 13.1

Question

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

Answer 1

The other answers are cool, here I give a straightforward proof, it might be more clearly for understanding the whole process.

The core idea here is that since each state can rollback to the previous state (the state before State S is itself), and each time it rollbacks to the previous state, the expected value of steps should increase the expectation of the previous state. The number of steps, which is ultimately expressed in the form of an infinite series.

Assuming that the action Left is selected in the first $t-1$ steps, and the action Right is selected in the $t$-th step, a total of $t$ steps are required to reach the State 2, where $ t \in [1, \infty) $:

$ E_{S\rightarrow 2}=1\cdot p^1+2\cdot p^1 (1-p)^1+3\cdot p^1 (1-p)^2+\cdots=p\sum_{t=1}^{\infty}t(1-p)^{t-1} $ $ =\frac{p}{1-p}\sum_{t=1}^{\infty}t(1-p)^t=\frac{p}{1-p}\cdot\frac{1-p}{p^2} = \frac{1}{p} $

The transition from State 2 to State 3 is divided into two cases, namely 2→3, 2→S→2→3, and if rollbacking from 2 to S, it is necessary to recursively calculate the expected number of steps from 2→S→2: $ E_{s\rightarrow 2} $, where $t$ is the total number of times to return to state S:

$ E_{2\rightarrow 3}=(1-p)+(2+E_{S\rightarrow2})p(1-p)+(3+2E_{S\rightarrow2})p^2(1-p)+\cdots $ $ =(1-p)+(1-p)\sum_{t=1}^{\infty}\left[1+t(1+E_{S\rightarrow2})\right]p^t$ $ =(1-p)+p+\frac{1-p^2}{p}\frac{p}{(1-p)^2} = 1+\frac{1+p}{1-p} = \frac{2}{1-p}$

$ E_{3\rightarrow G} $ can be obtained in the same way:

$ E_{3\rightarrow G}=p+(2+E_{2\rightarrow3})p(1-p)+(3+2E_{2\rightarrow3})p(1-p)^2+\cdots $ $ =p+p\sum_{t=1}^{\infty}\left[1+t(1+E_{2\rightarrow3})\right](1-p)^t $ $ = p+ p \left[ \frac{1-p}{p} + \frac{3-p}{1-p} \frac{1-p}{p^2} \right] = p+(1-p) + \frac{3-p}{p} = \frac{3}{p} $

Above we have calculated the expected number of steps for the three state transitions $ E_{S\rightarrow 2}, E_{2\rightarrow 3}, E_{3\rightarrow G} $, so the total expected value is:

$ E = E_{S\rightarrow 2} + E_{2\rightarrow 3} + E_{3\rightarrow G} = \frac{4}{p} + \frac{2}{1-p} $

To maximize the expectation, then

$ \left[\frac{4}{p} + \frac{2}{1-p}\right]^{\prime} = -\frac{4}{p^2}+\frac{2}{(1-p)^2} = 0 $

Get a solution that satisfies the condition: $ p=2-\sqrt{2}\approx 0.5858, E=6+4\sqrt{2} \approx 11.6568 $.

Answer 2

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[0] , results[1]
    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$$

Answer 3

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 $$

Answer 4

As Alex mentioned, this is a typical mean time to absorption type of problem in a Markov chain except each step incurs a negative reward. So, yet another way to solve this problem is to set up a system of equations. Let $v_1, v_2, v_3$ denote the mean reward starting from states 1, 2, and 3, respectively. Then we have:

$$ \begin{cases} v_1 =& (1-p)v_1 + pv_2 -1 \\ v_2 =& (1-p)v_3 + pv_1 -1 \\ v_3 =& (1-p)(v_2-1) \end{cases} $$

Solving this gives $v_1 = \frac{p^2-3p+4}{p(p-1)}$. Now, taking the derivative and setting it to 0 yields $p^* = 2-\sqrt{2}$