1
$\begingroup$

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

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ The expression $(p^2-2p+2)/(p(1-p))$ is positive for all, so I wouldn't rely on it... $\endgroup$
    – Kostya
    May 24 at 9:24
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Snowball
    May 25 at 19:39
  • $\begingroup$ @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 $\endgroup$
    – Kostya
    May 25 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.