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.