text: import numpy as np
  import matplotlib.pyplot as plt
  from numpy import linalg as LA
  from cProfile import label
  
  class cliffWalking():
      def __init__(self,start,end):
  #         action = [left up right down]
  #         action = [0 1 2 3]
          self.x = 12
          self.y = 4
          self.reward = 0
          self.states = np.arange(self.x*self.y).reshape(self.y,self.x)
          self.action_space = [0,1,2,3]
          self.size = self.x*self.y
          self.done = False
          self.state = start
          self.endstate = end
          self.Q = np.zeros(len(self.action_space)*self.size).reshape(self.size,len(self.action_space))
          
      def _step(self, action,reward):
          self.reward -= 1
  #         left
          pos = np.where(self.states == self.state)
          if (action==0):
              if (pos[1] == 0):
                  self.state = self.state
  #                 reward += 1
              else:
                  newPos = list(pos)
                  if (newPos[0] < 0):
                      newPos[0] = 0  
                  newPos = tuple(newPos)
                  self.state = int(self.states[newPos])
                  self.state = self.state - 1
                  
  #         right
          if (action==2):
              if (pos[1] == self.x-1):
                  self.state = self.state
  #                 reward += 1
              else:
                  newPos = list(pos)
                  if (newPos[0] < 0):
                      newPos[0] = 0  
                  newPos = tuple(newPos)
                  self.state = int(self.states[newPos])
                  self.state = self.state + 1
  #         up
          if (action==1):
              if (pos[0] == 0):
                  self.state = self.state
  #                 reward += 1
              else:
                  newPos = list(pos)
                  newPos[0] -=1
                  if (newPos[0] < 0):
                      newPos[0] = 0  
                  newPos = tuple(newPos)
                  self.state = int(self.states[newPos])
  #         down
          if (action==3):
              if (pos[0] == self.y-1):
                  self.state = self.state
  #                 reward += 1
              else:
                  newPos = list(pos)
                  newPos[0] +=1
                  if (newPos[0] < 0):
                      newPos[0] = 0  
                  newPos = tuple(newPos)
                  self.state = int(self.states[newPos])
          
          if (int(pos[0])==self.y-1):
              if (pos[1]>0 and pos[1]<self.x-1):
                  self.reward = -100
                  self.state = start
              
          if (self.state == self.endstate):
              self.reward = 0
              self.done = True
          
  #         print('new state: ',self.state, ', reward: ', reward)
          return self.state, self.reward, self.done
      
      def _reset(self):
          self.state = start
          self.done = False
          print('starting state: ', self.state)
      
      def _render(self):
          print('current state: ', self.state)
          
              
      def eGreedy(self,epsilon):
          m = 100
          n = epsilon * 100
          p = np.random.randint(m)
          if (p>(m-n-1)):
              epsilon = 1
          else:
              epsilon = 0
          return epsilon
      
      def plotQ(self,Q):
          plt.xlim(-0.5,self.x+0.5)
          plt.ylim(-self.y-0.5,0.5)
  
          for i in range(len(Q[:,0])):
              l = list(Q[i,:])
              a = l.index(max(l))
              pos = np.where(self.states == i)
  #             print('action:',a,'state',i)
              if (a == 0):
                  plt.arrow(int(pos[1])+0.1,-int(pos[0]),-0.2,0,head_width=0.2, head_length=0.2, fc='c', ec='c')     
              if (a == 1):
                  plt.arrow(int(pos[1]),-int(pos[0])-0.1,0,0.2,head_width=0.2, head_length=0.2, fc='c', ec='c')
              if (a == 2):
                  plt.arrow(int(pos[1])-0.1,-int(pos[0]),0.2,0,head_width=0.2, head_length=0.2, fc='c', ec='c')
              if (a == 3):
                  plt.arrow(int(pos[1]),-int(pos[0])+0.1,0,-0.2,head_width=0.2, head_length=0.2, fc='c', ec='c')
              
  
  def rlcliff(c,episode,step,alpha,gamma,epsilon,algo):
  
      num2 = []
      count = []
      count2 = []
      num_ges = []
      rnew = 0
      rew =[]
      mid = []
  
      if (algo==0):
          for j in range(episode):
              num = 0
              row = []
              reward = 0
              #init a starting state s
              c._reset()
              #select an action a from s using a policy pi derived from Q e-greedy
              e = c.eGreedy(epsilon)
              l = list(c.Q[c.state,:])
              a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
               
              row.append(c.state)
              for i in range(step):
          #         print('old_state: ',c.state,' action: ', a, ' epsilon:', e)
                  r = rnew
                  s = c.state
                  #execute a observe r,s'
                  snew,rnew,done = c._step(a, reward)
                  row.append(snew)
                   
                  #Derive pi from Q, then selection action a' from s'
                  e = c.eGreedy(epsilon)
                  l = list(c.Q[c.state,:])
                  anew = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
                   
                  #update Q_q
                  c.Q[s,a] = c.Q[s,a] + alpha * (rnew + gamma*c.Q[snew,anew] - c.Q[s,a])
                   
                  #s = s' and a = a'
                  a = anew
                   
                  num += 1
          #         print(c.Q)
                  if done:
                      if (j>0):
                          num_ges.append(num_ges[j-1]+num)
                      else:
                          num_ges.append(num)
                      count.append(j)
                      mid.append(r)
                      if (j>0 and j%10 == 0):
                          rew.append(1/float(10)*sum(mid))
                          mid = []
                          count2.append(j)
                      num2.append(num)
                      print('terminal state: ', c.state,'steps: ',num)
                      break
           
               
              num = 0
          return c.Q,row,rew,count,count2
      elif(algo == 1):
          for j in range(episode):
              num = 0
              row = []
              reward = 0
              #init a starting state s
              c._reset()
             
              row.append(c.state)
              for i in range(step):
                  r = rnew
          #         select an action a from s using a plicy pi derived from Q (epsilon greedy)
                  e = c.eGreedy(epsilon)
                  l = list(c.Q[c.state,:])
                  a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
                 
                  s = c.state
          #         execute a, observe r, s'
                  snew,rnew,done = c._step(a, reward)
                     
                  row.append(snew)
                     
                  #update Q
                  c.Q[s,a] = c.Q[s,a] + alpha*(r + gamma*max(c.Q[snew,:]) - c.Q[s,a])
                     
                  #s = s' and a = a'
                             
                  num += 1
          #         print(c.Q)
                  if done:
                      if (j>0):
                          num_ges.append(num_ges[j-1]+num)
                      else:
                          num_ges.append(num)
                      count.append(j)
                      mid.append(r)
                      if (j>0 and j%10 == 0):
                          rew.append(1/float(10)*sum(mid))
                          mid = []
                          count2.append(j)
                      num2.append(num)
                      print('terminal state: ', c.state,'steps: ',num)
                      break
             
                 
              num = 0
          return c.Q,row,rew,count,count2
  
  
  def plotPath(row,color,algo,endstate):
      x=[]
      y=[]
      dx =[]
      dy = []
      for k in range(len(row)):
          pos = np.where(c.states == row[k])
          y.append(int(-pos[0]))
          x.append(int(pos[1]))
          if (k+1 < len(row)):
              posnext = np.where(c.states == row[k+1])
              dy=(int(-posnext[0])-y[k]) - (int(-posnext[0])-y[k])*0.6
              dx=(int(posnext[1])-x[k]) - (int(posnext[1])-x[k])*0.6
              plt.arrow(int(x[k]), int(y[k]), dx, dy,head_width=0.2, head_length=0.5, fc=color, ec=color)
         
      plt.plot(x,y,'ro',label = algo)
      plt.plot(0,-3,'cx',label = 'start')
      plt.plot(11,-3,'kx',label = 'original goal')
      plt.plot(endstate[1],-endstate[0],'gx',label = 'goal')   
      plt.grid()
      plt.legend()
      plt.plot(x,y,color)
  
  start = 36
  end = 47
  episode = 1000
  step = 100000
  alpha = 0.1
  gamma = 1
  epsilon = 0.1
  c = cliffWalking(start,end)
  # 2a)
  # For all comparisons, plot the learning graph having episode as x-axis, reward per episode as y-axis, smoothed by
  # averaging the reward sums from 10 successive episodes.
  #-------------------------------------------------------------------------------
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = rlcliff(c, episode, step, alpha, gamma, epsilon, 0)
  c=cliffWalking(start,end)
  Q_q,row_q,rew_q,count_q,count2_q = rlcliff(c, episode, step, alpha, gamma, epsilon, 1)
  
  plt.plot(count2,rew,label='SARSA')
  plt.plot(count2_q,rew_q,label='Q-learning')
  plt.xlabel('#episodes')
  plt.ylabel('#reward per episode')
  plt.legend()
  plt.grid()
  
  plt.figure(4)
  plt.subplot(211)
  c.plotQ(Q)
  plt.grid()
  plt.subplot(212)
  c.plotQ(Q_q)
  plt.grid()
  
  
  # print('average reward SARSA',sum(rew)/episode)
  # print('average reward Q-Learning',sum(rew_q)/episode)
  
  # plt.show()
  
  #-------------------------------------------------------------------------------
  # 2b)
  # Propose a schedule that gradually reduces epsilon, starting from e.g. epsilon= 1. Be creative! Then redo question a) using
  # such schedule of epsilon instead of the fixed value.
  
  plt.figure(2)
  epsilon = np.array([1,0.9,0.8,0.7,0.6,0.5,0.4,0.3,0.2,0.1])
  epsilon = 0.1*epsilon
  epsilonint = 1
  epsilon = []
  # epsilon = np.ones(10)
  def rlcliffdyn(c,episode,step,alpha,gamma,epsilon,algo):
      
      num2 = []
      count = []
      count2 =[]
      num_ges = []
      rnew = 0
      rew =[]
      epsilon=[]
      mid = []
      
      if (algo==0):
          for j in range(episode):
              num = 0
              row = []
              reward = 0
              #init a starting state s
              c._reset()
              #select an action a from s using a policy pi derived from Q e-greedy
              epsilon.append(1/float(j+1)*epsilonint)
              e = c.eGreedy(epsilon[j])
              l = list(c.Q[c.state,:])
              a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
                   
              row.append(c.state)
              for i in range(step):
          #         print('old_state: ',c.state,' action: ', a, ' epsilon:', e)
                  r = rnew
                  s = c.state
                  #execute a observe r,s'
                  snew,rnew,done = c._step(a, reward)
                  row.append(snew)
                       
                  #Derive pi from Q, then selection action a' from s'
                  e = c.eGreedy(epsilon[j])
                  l = list(c.Q[c.state,:])
                  anew = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
                       
                  #update Q_q
                  c.Q[s,a] = c.Q[s,a] + alpha * (rnew + gamma*c.Q[snew,anew] - c.Q[s,a])
                       
                  #s = s' and a = a'
                  a = anew
                       
                  num += 1
          #         print(c.Q)
                  if done:
                      if (j>0):
                          num_ges.append(num_ges[j-1]+num)
                      else:
                          num_ges.append(num)
                      mid.append(r)
                      if (j>0 and j%10 == 0):
                          rew.append(1/float(10)*sum(mid))
                          mid = []
                          count2.append(j)
                      count.append(j)
                      num2.append(num)
                      print('terminal state: ', c.state,'steps: ',num)
                      break
               
                   
              num = 0
          return c.Q,row,rew,count,epsilon,count2
      elif(algo == 1):
          for j in range(episode):
              num = 0
              row = []
              reward = 0
              #init a starting state s
              c._reset()
              epsilon.append(1/float(j+1) *epsilonint)
                 
              row.append(c.state)
              for i in range(step):
                  r = rnew
          #         select an action a from s using a plicy pi derived from Q (epsilon greedy)
                  e = c.eGreedy(epsilon[j])
                  l = list(c.Q[c.state,:])
                  a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
                     
                  s = c.state
          #         execute a, observe r, s'
                  snew,rnew,done = c._step(a, reward)
                         
                  row.append(snew)
                         
                  #update Q
                  c.Q[s,a] = c.Q[s,a] + alpha*(r + gamma*max(c.Q[snew,:]) - c.Q[s,a])
                         
                  #s = s' and a = a'
                                 
                  num += 1
          #         print(c.Q)
                  if done:
                      if (j>0):
                          num_ges.append(num_ges[j-1]+num)
                      else:
                          num_ges.append(num)
                      count.append(j)
                      mid.append(r)
                      if (j>0 and j%10 == 0):
                          rew.append(1/float(10)*sum(mid))
                          mid = []
                          count2.append(j)
                      num2.append(num)
                      print('terminal state: ', c.state,'steps: ',num)
                      if (num < 18):
                          print(row)
                      break
                 
                     
              num = 0
          return c.Q,row,rew,count,epsilon,count2
      
  c = cliffWalking(start,end)
  Q,row,rew,count,epsilon,count2= rlcliffdyn(c, episode, step, alpha, gamma, epsilon, 0)
  c=cliffWalking(start,end)
  Q_q,row_q,rew_q,count_q,epsilon_q,count2_q = rlcliffdyn(c, episode, step, alpha, gamma, epsilon, 1)
  plt.subplot(211)
  plt.plot(count,epsilon)
  plt.grid()
  plt.ylabel('epsilon')
    
  plt.subplot(212)
  plt.plot(count2,rew,label='SARSA')
  plt.plot(count2_q,rew_q,label='Q-learning')
    
  plt.legend()
  plt.xlabel('#episodes')
  plt.ylabel('#reward per episode')
  print('average reward SARSA',sum(rew)/episode)
  print('average reward Q-Learning',sum(rew_q)/episode)
  plt.grid()
  
  
  # 2c)
  #-------------------------------------------------------------------------------
  c = cliffWalking(start,end)
  c._render()
  # c._reset()
  epsilon = 0.1
  lamb = np.array([0.9,0.8,0.7,0.5,0.2])
  plt.figure(3)
  def SarsaLambda(c,episode,step,lamb):
      rew = []
      rnew = 0
      count = []
      count2 = []
      mid = []
      for i in range(episode):
     
          row = []
          reward = 0
             
          c._reset()
             
          E = np.zeros(c.size*len(c.action_space)).reshape(c.size,len(c.action_space))
             
          e = c.eGreedy(epsilon)
          l = list(c.Q[c.state,:])
          a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
             
          for j in range(step):
              r = rnew
              s = c.state
              snew,rnew,done = c._step(a, reward)
              row.append(snew)
                 
              e = c.eGreedy(epsilon)
              l = list(c.Q[c.state,:])
              anew = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l)) 
                 
              delta = rnew + gamma*c.Q[snew,anew]-c.Q[s,a]
                 
              E[s,a]= E[s,a] + 1
      #         E[s,a]=(1-alpha)*E[s,a] +1
      #         E[s,a] = 1
                 
              for m in range(c.size):
                  for n in range(len(c.action_space)):
                      c.Q[m,n] = c.Q[m,n] + alpha*delta*E[m,n]
                      E[m,n] = gamma*lamb*E[m,n]
                 
              a = anew
              if done:
                  print('endsate:',c.state)
                  mid.append(r)
                  if (i>0 and i%10 == 0):
                      rew.append(1/float(10)*sum(mid))
                      mid = []
                      count2.append(i)
      #             print(row)
                  break
             
      return c.Q,row,rew,count,count2
                
  plt.subplot(211)
     
  Q,row,rew,count,count2 = SarsaLambda(c, episode, step, lamb[0])
  plt.plot(count2,rew,label='SARSA lambda = 0.9')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = SarsaLambda(c, episode, step, lamb[1])
  plt.plot(count2,rew,label='SARSA lambda = 0.8')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = SarsaLambda(c, episode, step, lamb[2])
  plt.plot(count2,rew,label='SARSA lambda = 0.7')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = SarsaLambda(c, episode, step, lamb[3])
  plt.plot(count2,rew,label='SARSA lambda = 0.5')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = SarsaLambda(c, episode, step, lamb[4])
  plt.plot(count2,rew,label='SARSA lambda = 0.2')
     
  plt.grid()
  plt.xlabel('#episodes')
  plt.ylabel('#reward per episode')
  plt.legend()
     
  def QLambda(c,episode,step,lamb):
      rew = []
      rnew = 0
      count = []
      count2 = []
      mid = []
      for i in range(episode):
     
          row = []
          reward = 0
             
          c._reset()
             
          E = np.zeros(c.size*len(c.action_space)).reshape(c.size,len(c.action_space))
             
          e = c.eGreedy(epsilon)
          l = list(c.Q[c.state,:])
          a = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l))
             
             
          for j in range(step):
              r = rnew
              s = c.state
              snew,rnew,done = c._step(a, reward)
              row.append(snew)
                 
              e = c.eGreedy(epsilon)
              l = list(c.Q[c.state,:])
              anew = e*np.random.randint(len(c.action_space)) + (1-e)*l.index(max(l)) 
              aopt = l.index(max(l)) 
                 
              delta = rnew + gamma*c.Q[snew,aopt]-c.Q[s,a]
                 
              E[s,a]= E[s,a] + 1
      #         E[s,a]=(1-alpha)*E[s,a] +1
      #         E[s,a] = 1
                 
              for m in range(c.size):
                  for n in range(len(c.action_space)):
                      c.Q[m,n] = c.Q[m,n] + alpha*delta*E[m,n]
                      if (anew == aopt):
                          E[m,n] = gamma*lamb*E[m,n]
                      else:
                          E[m,n] = 0
                             
              a = anew
              if done:
                  print('endsate:',c.state)
                  mid.append(r)
                  if (i>0 and i%10 == 0):
                      rew.append(1/float(10)*sum(mid))
                      mid = []
                      count2.append(i)
                  count.append(i)
      #             print(row)
                  break
             
      return c.Q,row,rew,count,count2
     
  plt.subplot(212)
     
  Q,row,rew,count,count2 = QLambda(c, episode, step, lamb[0])
  plt.plot(count2,rew,label='Q(lambda) lambda = 0.9')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = QLambda(c, episode, step, lamb[1])
  plt.plot(count2,rew,label='Q(lambda) lambda = 0.8')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = QLambda(c, episode, step, lamb[2])
  plt.plot(count2,rew,label='Q(lambda) lambda = 0.7')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = QLambda(c, episode, step, lamb[3])
  plt.plot(count2,rew,label='Q(lambda) lambda = 0.5')
  c = cliffWalking(start,end)
  Q,row,rew,count,count2 = QLambda(c, episode, step, lamb[4])
  plt.plot(count2,rew,label='Q(lambda) lambda = 0.2')
  plt.legend()
  plt.xlabel('#episodes')
  plt.ylabel('#reward per episode')
  plt.grid()
  plt.show()
  
  
  
      