Question

For the environment shown in Figure 17.1, find all the threshold values for R(s) such that the optimal policy changes when the threshold is crossed. You will need a way to calculate the optimal policy and its value for fixed R(s).

 

Figure 17.1

Answer 1

• For any two adjacent policies that differ, run binary search on the step cost to pinpoint the threshold value.
• Convince yourself that you haven’t missed any policies, either by using too coarse an increment in step size (0.02), or by stopping too soon (1.0).

 

One useful observation in this context is that the expected total reward of any fixed policy is linear in r, the per-step reward for the empty states. Imagine drawing the total reward of a policy as a function of r x a straight line. Now draw all the straight lines corresponding to all possible policies. The reward of the optimal policy as a function of r is just the max of all these straight lines. Therefore it is a piece wise linear, convex function of r. 

Hence there is a very efficient way to find all the optimal policy regions:

• For any two consecutive values of r that have different optimal policies, find the optimal policy for the midpoint. Once two consecutive values of r give the same policy, then the interval between the two points must be covered by that policy.
• Repeat this until two points are known for each distinct optimal policy.
• Suppose (ra1, va1) and (ra2, va2) are points for policy a, and (rb1, vb1) and (rb2, vb2) are the next two points, for policy b. Clearly, we can draw straight lines through these pairs of points and find their intersection. This does not mean, however, that there is no other optimal policy for the intervening region. We can determine this by calculating the optimal policy for the intersection point. If we get a different policy, we continue the process.

 

The policies and boundaries derived from this procedure are shown in Figure S17.1. The figure shows that there are nine distinct optimal policies! Notice that as r becomes more negative, the agent becomes more willing to dive straight into the –1 terminal state rather than face the cost of the detour to the +1 state.

 

The somewhat ugly code is as follows. That because the lines for neighboring policies are very nearly parallel, numerical instability is a serious problem.

 

Figure S17.1

 

 

• For any two adjacent policies that differ, run binary search on the step cost to pinpoint the threshold value.
• Convince yourself that you haven’t missed any policies, either by using too coarse an increment in step size (0.02), or by stopping too soon (1.0).