In Barto and Sutton's book, it's written that we have two types of updates in dynamic programming

  1. Update out-of-place
  2. Update in-place

The update in-place is the faster one. Why is that the case?

This is the pseudocode that I used to test it.

if in_place:
    state_values = new_state_values
    state_values = new_state_values.copy()
old_state_values = state_values.copy()

for i in range(WORLD_SIZE):
    for j in range(WORLD_SIZE):
        value = 0
        for action in ACTIONS:
            (next_i, next_j), reward = step([i, j], action)
            value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
        new_state_values[i, j] = value

max_delta_value = abs(old_state_values - new_state_values).max()
if max_delta_value < 1e-4:

Why is the in-place version faster, and what is the difference? What I think is that it is only better for storage usage, I don't understand the speed increase part.


When you make updates in-place, then some of the entries in state_values[next_i, next_j] that you are referencing here

value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])

will already be updated earlier in the same loop. Which means you get to use the latest and likely more accurate values earlier.

The strength of this effect varies depending on the order that states and actions are visited. If you can manage to visit them in reverse order that they would appear in natural trajectories, then the speed improvement will be very noticeable.


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.