# Q Learning for FrozenLake environment not converging to V* values from Value Iteration

I am trying to learn tabular Q learning, value iteration using the classical algorithms (no neural networks) by using a table of states and actions. I was trying it out on FrozenLake environment in OpenAI. It's a very simple environment where the task is to reach a G starting from a source S avoiding holes H and just following the frozen path which is F. The 4x4 FrozenLake grid looks like this

 SFFF FHFH FFFH HFFG

I am working with the slippery version where the agent if it takes a step has equal probability of either going in the direction it intends or slipping sideways perpendicular to the original direction (if that position is in grid). Holes are terminal states and goal is a terminal state.

Now I first tried value iteration which converges to following set of values for the states [0.0688909 0.06141457 0.07440976 0.05580732 0.09185454 0. 0.11220821 0. 0.14543635 0.24749695 0.29961759 0. 0. 0.3799359 0.63902015 0. ]

I also coded policy iteration and it also gives me the same result. So I am pretty confident that this value function is correct.

Now I tried to code the Q learning algorithm, here is my code for Q learning algorithm

def get_action(Q_table, state, epsilon):
"""
Uses e-greedy to policy to return an action corresponding to state

Args:
Q_table: numpy array containing the q values
state: current state
epsilon: value of epsilon in epsilon greedy strategy
env: OpenAI gym environment
"""
return env.action_space.sample() if np.random.random() < epsilon else np.argmax(Q_table[state])

def tabular_Q_learning(env):
"""
Returns the optimal policy by using tabular Q learning

Args:
env: OpenAI gym environment

Returns:
(policy, Q function, V function)
"""

# initialize the Q table
#
# Implementation detail:
# A numpy array of |x| * |a| values

Q_table = np.zeros((env.nS, env.nA))

# hyperparameters
epsilon = 0.9
episodes = 500000
lr = 0.81

for _ in tqdm_notebook(range(episodes)):
# initialize the state
state = env.reset()

if episodes / 1000 > 21:
epsilon = 0.1

t = 0
while True: # for each step of the episode
# env.render()
# print(observation)

# choose a from s using policy derived from Q
action = get_action(Q_table, state, epsilon)

# take action a, observe r, s_dash
s_dash, r, done, info = env.step(action)

# Q table update
Q_table[state][action] += lr * (r + gamma * np.max(Q_table[s_dash]) - Q_table[state][action])

state = s_dash

t += 1

if done:
# print("Episode finished after {} timesteps".format(t+1))
break
# print(Q_table)

policy = np.argmax(Q_table, axis=1)
V = np.max(Q_table, axis=1)

return policy, Q_table, V


I tried running it and it converges to a different set of values which is following [0.26426802 0.03656142 0.12557195 0.03075882 0.35018374 0. 0.02584052 0. 0.37657211 0.59209091 0.15439031 0. 0. 0.60367728 0.79768863 0. ]

I am not getting, what is going wrong. The implementation of Q learning is pretty straightforward. I checked my code, it seems right.

• Your learning rate seems pretty high for a stochastic environment, and I don't see anywhere that it decays. Have you tried with lower lr? – Neil Slater Oct 14 at 17:57
• hey @NeilSlater It worked thanks, I just put a decay rate on learning rate and it converged. – abkds Oct 14 at 18:20

I was able to solve the problem with the help of comment from @NeilSlater. The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of $$-0.00005$$ on the learning rate lr and subsequently Q-Learning also converged to the same value as value iteration.

• You may also have been able to work with a lower fixed learning rate of e.g. 0.01 - that should be low enough to converge to an optimal policy, and result in close enough to true Q values that you could easily see the similarity with the dynamic programming approaches. – Neil Slater Oct 15 at 8:49