Temporal Difference Learning Not Converging

I'm trying to implement a $Q(\lambda)$ algorithm from this paper (warning: link is a download of a PDF) and can't seem to get it to find anything that close to the optimal policy. From what I can tell, it looks like it's getting to about 50% of optimal and then getting stuck, no matter how many times I run it. If possible, I'd like for someone to look over my script and see if I'm doing anything incorrectly. I'm not a coder, so it's not very pretty. It may be a little over-commented, but I wanted to make sure my intentions were clear when posting.

import random

# This contains the class QLearn, which houses all of the associated functions for Q-Learning

class AutoVivification(dict):
def __getitem__(self, item):
try:
return dict.__getitem__(self, item)
except KeyError:
value = self[item] = type(self)()
return value

class QLearn:
# Initialize the agent. Actions is a list of allowable prices.
def __init__(self, actions = [1,2,3,4,5,6,7,8,9,10], state = 15, action = 10, discount = 0.999, lamb = 0.9):
self.actions = actions
self.state = state
self.action = action
self.discount = discount
self.lamb = lamb
self.visits = {}
self.history = {}

# Gets the reward realized at a given state and action, along with the new state
def getNextState(self, sold):
newstate = self.state - sold
if newstate < 0:
newstate = 0
return newstate

# Multiply sold and price to get revenue reward
def getReward(self,sold):
if sold > self.state:
reward = self.state * self.action
else:
reward = self.action * sold
return reward

# Gets the q value for a given state for the given k and t
def getQ(self, k, t, state, action):
return self.q[(k,t)].get((state,action), 0.0)

# Gets the eligibility trace for a given state for the given k and t
def getET(self, k, t, state,action):
return self.et[(k,t)].get((state,action), 0.0)

# Choose which action to take in the next time period
def chooseAction(self, k, t):
# Decide if to explore or exploit
if random.random() < (1/float(k)):
# Exploring, so a random action is chosen
newaction = random.choice(self.actions)
explore = True
self.history[t] = (self.state,self.action)
q = [self.getQ(k, t+1, self.nextState, action) for action in self.actions]
maxQ = max(q)
count = q.count(maxQ)
# If there are two Q values that are the same, choose a random one
if count > 1:
best = [i for i in range(len(self.actions)) if q[i] == maxQ]
i = random.choice(best)
else:
i = q.index(maxQ)
self.bestAction = self.actions[i]
else:
# Get a list of Q values for every action
q = [self.getQ(k, t+1, self.nextState, action) for action in self.actions]
maxQ = max(q)
count = q.count(maxQ)
# If there are two Q values that are the same, choose a random one
if count > 1:
best = [i for i in range(len(self.actions)) if q[i] == maxQ]
i = random.choice(best)

else:
i = q.index(maxQ)
#print "Index:", i
explore = False
newaction = self.actions[i]
# Record decision for k and t in history
self.history[t] = (self.state,self.action)
return newaction, explore

# Choose which action to take in the next episode
def nextEpisodeAction(self, k):
# Decide if to explore or exploit
if random.random() < (1/float(k)):
# Exploring, so a random action is chosen
newaction = random.choice(self.actions)
explore = True
q = [self.getQ(k+1, 10, 15, action) for action in self.actions]
maxQ = max(q)
count = q.count(maxQ)
# If there are two Q values that are the same, choose a random one
if count > 1:
best = [i for i in range(len(self.actions)) if q[i] == maxQ]
i = random.choice(best)
else:
i = q.index(maxQ)
self.bestAction = self.actions[i]
else:
# Get a list of Q values for every action
q = [self.getQ(k+1, 10, 15, action) for action in self.actions]
maxQ = max(q)
count = q.count(maxQ)
# If there are two Q values that are the same, choose a random one
if count > 1:
best = [i for i in range(len(self.actions)) if q[i] == maxQ]
i = random.choice(best)
else:
i = q.index(maxQ)
explore = False
newaction = self.actions[i]
return newaction, explore

# Calculate the temporal difference error
def TDError(self, k, t):
if t == 15:
delta = self.reward + self.discount*0 - self.getQ(k,t,self.state,self.action)
else:
if self.explore:
delta = self.reward + self.discount*self.getQ(k,t+1,self.nextState,
self.bestAction) - self.getQ(k,t,self.state,self.action)
else:
delta = self.reward + self.discount*self.getQ(k,t+1,self.nextState,
self.nextAction) - self.getQ(k,t,self.state,self.action)
return delta

# Update the eligibility trace for the current state
def updateCurrentET(self, k, t, state, action):
self.et[(k,t)][(state,action)] = 1

# Update the Q values for the next episode for all state-action pairs used during this episode
def updateQs(self, k, t):
for i in range(t,0,-1):
self.q[(k+1,t)][self.history[i]] = self.q[(k,i)].get(self.history[i],0.0) + \
(1 / float(1 + self.visits.get(self.history[i],0))) * self.tdError * \
self.et[t].get(self.history[i],0.0)

# Update the eligibility traces for all state-action pairs used in the episode
def updateETs(self, k, t):
# Set all to zero if exploration
if self.explore:
for i in range(t,0,-1):
self.et[t+1][self.history[i]] = 0
else:
for i in range(t,0,-1):
self.et[t+1][self.history[i]] =  self.lamb * self.et[t].get(self.history[i],0.0)

# Assign the next state and action to the current state and action
def stepForward(self):
self.state = self.nextState
self.action = self.nextAction


This next section is my simulation.

import random
from qlearn.qlearn import QLearn, AutoVivification

# This simulates the process by which sales are realized and applies the Q-Learning algorithm to it
# Each series of episodes is repeated 1000 times in order to find the average revenue realized across all episodes

def main():
# Define periods and episodes, instantiate the agent
periods = 10
episodes = 200
agent = QLearn()
revHistory = []
firstSold = getSold(1,agent.action,agent.state)
for k in range(1,episodes+1,1):
revenue = 0
# Process for first episode
if k == 1:
for t in range(1,periods+1,1):
# Process for first period and episode
if t == 1:
revenue = revenue + firstPeriodandEpisode(agent, firstSold)
# Process for last period
elif t == periods:
revenue = revenue + lastPeriod(agent, k, t)
# Process for all other periods
else:
revenue = revenue + update(agent, k, t)
else:
for t in range(1,periods+1,1):
# Process for first period
if t == 1:
revenue = revenue + firstPeriod(agent, k, t)
# Process for last period
elif t == periods:
revenue = revenue + lastPeriod(agent, k, t)
# Process for all other periods
else:
revenue = revenue + update(agent, k, t)
# Updates number of visits to each state-action pair at the end each episode
for i in range(1,periods+1,1):
agent.visits[agent.history[i]] = agent.visits.get(agent.history[i],0) + 1
revHistory.append(revenue)
# Returns the final revenue realized
return revHistory[-1]

def firstPeriodandEpisode(agent, sold):
# Creates dictionaries for eligibility traces and Q values
agent.et = AutoVivification()
agent.q = AutoVivification()
# Gets the next state based on number sold
agent.nextState = agent.getNextState(sold)
# Calculates the reward by multiplying the number sold by the price
agent.reward = agent.getReward(sold)
# Chooses the next action by finding the maximum Q value
agent.nextAction, agent.explore = agent.chooseAction(k=1, t=1)
# Calculates the temporal difference error for the action
agent.tdError = agent.TDError(k=1,t=1)
# Assigns the number 1 to the current eligibility trace for the current state and action
agent.et[1][(agent.state,agent.action)] = 1
agent.updateQs(k=1,t=1)
agent.updateETs(k=1,t=1)
agent.stepForward()
return agent.reward

def update(agent, k, t):
# Gets number sold based on the equation in getSold()
periodSold = getSold(t, agent.action, agent.state)
# Gets the next state based on number sold
agent.nextState = agent.getNextState(periodSold)
# Calculates the reward by multiplying the number sold by the price
agent.reward = agent.getReward(periodSold)
# Chooses the next action by finding the maximum Q value
agent.nextAction, agent.explore = agent.chooseAction(k, t)
# Calculates the temporal difference error for the action
agent.tdError = agent.TDError(k,t)
# Assigns the number 1 to the current eligibility trace for the current state and action
agent.et[t][(agent.state,agent.action)] = 1
agent.updateQs(k,t)
agent.updateETs(k,t)
agent.stepForward()
return agent.reward

def lastPeriod(agent, k, t):
# Gets number sold based on the equation in getSold()
periodSold = getSold(t, agent.action, agent.state)
# Gets the next state based on number sold
agent.nextState = agent.getNextState(periodSold)
# Calculates the reward by multiplying the number sold by the price
agent.reward = agent.getReward(periodSold)
# Chooses the next action by finding the maximum Q value
agent.nextAction, agent.explore = agent.chooseAction(k, t)
# Calculates the temporal difference error for the action
agent.tdError = agent.TDError(k,t)
# Assigns the number 1 to the current eligibility trace for the current state and action
agent.et[t][(agent.state,agent.action)] = 1
agent.updateQs(k,t)
agent.updateETs(k,t)
# Gets the action for the beginning of the next episode and makes it the current state
agent.action, agent.explore = agent.nextEpisodeAction(k)
# Sets current state to the beginning state
agent.state = 15
return agent.reward

def firstPeriod(agent, k, t):
# All eligibility traces to 0
agent.et = AutoVivification()
# Clear state-action history
agent.history = {}
# Gets number sold based on the equation in getSold()
periodSold = getSold(t, agent.action, agent.state)
# Gets the next state based on number sold
agent.nextState = agent.getNextState(periodSold)
# Calculates the reward by multiplying the number sold by the price
agent.reward = agent.getReward(periodSold)
# Chooses the next action by finding the maximum Q value
agent.nextAction, agent.explore = agent.chooseAction(k, t)
# Calculates the temporal difference error for the action
agent.tdError = agent.TDError(k,t)
# Assigns the number 1 to the current eligibility trace for the current state and action
agent.et[t][(agent.state,agent.action)] = 1
agent.updateQs(k,t)
agent.updateETs(k,t)
agent.stepForward()
return agent.reward

# Gets the number sold base on the time period, the action, and the state
def getSold(t, action, state):
if state == 0:
sold = 0
else:
# Equation that simulates the amount sold
sold = .3 + .25*t - .014*action
if sold < 0:
sold = 0
return int(round(sold,0))

if __name__ == "__main__":
simRev = []
for i in range(1,1001,1):
simRev.append(main())
# Prints the average final revenue over all simulations
print reduce(lambda x, y: x + y, simRev) / float(len(simRev))


For quick reference, here are the steps outlined in the referenced paper: