# Q-learned policy differs from double-Q-learned policy

I implemented Q-learning and double-Q-learning as presented in Sutton's "Reinforcement Learning: An Introduction". I test the algorithms on the OpenAI cliff walking gym and analyze the resulting policies after 500 episodes.

I was expecting the two policies to be the same, but actually the policies differ:

Policy learned with Q-learning:
(x represent the steps taken by a greedy policy evaluation, T is target, C is cliff)
o  o  o  o  o  o  o  o  o  o  o  o
o  o  o  o  o  o  o  o  o  o  o  o
x  x  x  x  x  x  x  x  x  x  x  x
x  C  C  C  C  C  C  C  C  C  C  T

Policy learned with double-Q-learning:
(x represent the steps taken by a greedy policy evaluation, T is target, C is cliff)
x  x  x  x  x  x  x  x  x  x  x  x
x  o  o  o  o  o  o  o  o  o  o  x
x  o  o  o  o  o  o  o  o  o  o  x
S  C  C  C  C  C  C  C  C  C  C  T


The policy learned from double-Q-learning is not the optimal-greedy, but a "safer" policy that walks the agent the furthest from the cliff. This policy is, in fact, identical to the one the book uses to present the difference between SARSA and Q-learning.

From these considerations, it would seem that double-Q-learning is learning an on-line policy instead of the off-line one that I was searching. Could this be caused by an implementation error, or is this the expected behavior of the learning method?

This is my learning-step implementation of the double-Q-learning (in python):

# Take a step
if np.random.uniform() < 1.0-epsilon:
action = np.argmax(Q1[state]+Q2[state])
else:
action = np.random.randint(0, env.action_space.n)
next_state, reward, done, _ = env.step(action)

# TD update
if np.random.uniform() < 0.5:
next_best_action_Q1 = np.argmax(Q1[next_state])
Q1[state][action] += alpha * (reward + discount_factor * Q2[next_state][next_best_action_Q1] - Q1[state][action] )
else:
next_best_action_Q2 = np.argmax(Q2[next_state])
Q2[state][action] += alpha * (reward + discount_factor * Q1[next_state][next_best_action_Q2] - Q2[state][action] )
state = next_state


Q1 and Q2 are initialized to zero value for all pairs (state, action). The policy used for the action selection is epsilon-greedy on the sum of the value estimates Q1 and Q2.