Artificial Intelligence in Games Assignment 2

import  numpy  as  np

import   contextlib

#  Configures   numpy  print   options

@contextlib . contextmanager

def     printoptions (* args ,   ** kwargs ) :

original  =  np . get  printoptions ()

np . set  printoptions (* args ,   ** kwargs )

try :

yield

finally :

np . set  printoptions (* * original )

class   EnvironmentModel :

def       in it     ( self  ,   n   states  ,   n   actions ,   seed=None ) :

self . n   states  =  n   states

self . n   actions  =  n   actions

self . random  state  =  np . random . RandomState( seed )

def  p( self  ,   next   state  ,   state ,   action ) :

raise   NotImplementedError ()

def  r ( self  ,   next   state  ,   state ,   action ) :

raise   NotImplementedError ()

def  draw( self  ,   state ,   action ) :

p  =   [ self . p( ns ,   state ,   action )   for   ns   in  range( self . n  states ) ]

next  state  =  self . random  state . choice ( self . n  states  ,   p=p)

reward  =  self . r ( next  state  ,   state ,   action )

return   next   state  ,   reward

class   Environment ( EnvironmentModel ) :

def       in it     ( self  ,   n   states  ,   n   actions ,   max   steps ,   pi ,   seed=None ) :

EnvironmentModel .     in it     ( self  ,   n  states  ,   n  actions ,   seed )

self . max   steps  =  max   steps

self . pi  =  pi

if   self . pi   is   None :

self . pi  =  np . full ( n  states  ,   1./ n  states )

def  reset ( self ) :

self . n   steps  =  0

self . state  =  self . random  state . choice ( self . n  states  ,   p=self . pi )

return   self . state

def  step ( self  ,   action ) :

if   action  <  0  or   action  >=  self . n   actions :

raise   Exception ( ’ Invalid   action . ’ )

self . n   steps  +=  1

done  =  ( self . n  steps  >=  self . max  steps )

self . state ,   reward  =  self . draw( self . state ,   action )

policy  =  np . array ( [ actions [ a ]   for   a  in   policy [: − 1]])

print ( policy . reshape ( self . lake . shape ))

print ( ’ Value : ’ )

with     printoptions ( precision =3,  suppress=True ) :

print ( value [: − 1]. reshape ( self . lake . shape ))

def  play ( env ) :

actions  =   [ ’w’ ,   ’a ’ ,   ’ s ’ ,   ’d ’ ]

state  =  env . reset ()

env . render ()

done  =  False

while  not  done :

c  =  input( ’/nMove :   ’ )

if   c  not  in   actions :

raise   Exception ( ’ Invalid   action ’ )

state ,   r ,   done  =  env . step ( actions . index ( c ))

env . render ()

print ( ’Reward :   {0} . ’ . format( r ))

The class EnvironmentModel represents a model of an environment.  The constructor of this class receives a number of states, a number of actions, and a seed that controls the pseudorandom number generator.  Its subclasses must implement two methods: p and r. The method p returns the probability of transitioning from state to next state given action . The method r returns the expected reward in having transitioned from state to next state given action . The method draw receives a pair of state and action and returns a state drawn according to p together with the corresponding expected reward.  Note that states and actions are represented by integers starting at zero. We highly recommend that you follow the same convention, since this will facilitate immensely the implementation of reinforcement learning algorithms. You can use a Python dictionary (or equivalent data structure) to map (from and to) integers to a more convenient representation when necessary.  Note that, in general, agents may receive rewards drawn probabilistically by an environment, which is not supported in this simplified implementation.

The class Environment  represents an interactive environment and inherits from  EnvironmentModel.  The constructor of this class receives a number of states, a number of actions, a maximum number of steps for interaction, a probability distribution over initial states, and a seed that controls the pseudorandom number generator.  Its subclasses must implement two methods:  p  and  r, which were  already explained above.  This class has two new methods:  reset  and step.  The method  reset  restarts the interaction between the agent and the environment by setting the number of time steps to zero and drawing a state according to the probability distribution over initial states.  This state is stored by the class.  The method step receives an action and returns a next state drawn according to p, the corresponding expected reward, and a flag variable.  The new state is stored by the class.  This method also keeps track of how many steps have been taken.  Once the number of steps matches or exceeds the pre-defined maximum number of steps, the flag variable indicates that the interaction should end.

The class FrozenLake represents the frozen lake environment. Your task is to implement the methods p  and r  for this class.  The constructor of this class receives a matrix that represents a lake, a probability that the agent will slip at any given time step, a maximum number of steps for interaction, and a seed that controls the pseudorandom number generator.  This class overrides the method  step  to indicate that the interaction should also end when the absorbing state is reached.  The method render is capable of rendering the state of the environment or a pair of policy and value function. Your implementation must similarly be capable of receiving any matrix that represents a lake.

The function play can be used to interactively test your implementation of the environment.

Important:  Implementing the  frozen lake environment is deceptively simple.  The file p.npy  contains  a numpy.array with the probability to be returned by the method p for each combination of next  state , state, and action in the small frozen lake. You should load this file using numpy.load to check your implementation. The tiles are numbered in row-major order, with the absorbing state coming last. The actions are numbered in the following order: up, left, down, and right.

for   i   in  range( max   episodes ) :

s  =  env . reset ()

#  TODO:

policy  =  q . argmax( axis =1)

value  =  q . max( axis =1)

return   policy ,   value

def  q   learning (env ,   max   episodes ,   eta ,  gamma,   epsilon  ,   seed=None ) :

random  state  =  np . random . RandomState( seed )

eta  =  np . linspace ( eta ,   0 ,   max  episodes )

epsilon  =  np . linspace ( epsilon  ,   0 ,   max  episodes )

q  =  np . zeros (( env . n  states  ,   env . n  actions ))

for   i   in  range( max   episodes ) :

s  =  env . reset ()

#  TODO:

policy  =  q . argmax( axis =1)

value  =  q . max( axis =1)

return   policy ,   value

The function sarsa  receives an environment,  a maximum number of episodes, an  initial  learning  rate, a discount factor, an initial  exploration factor, and an (optional) seed that controls the pseudorandom number generator.   Note  that  the learning rate  and exploration factor decrease linearly as the number of episodes increases (for instance, eta[i] contains the learning rate for episode i).

The function q learning receives an environment, a maximum number of episodes, an initial learning rate, a discount factor, an initial exploration factor, and an (optional) seed that controls the pseudorandom number generator.   Note  that  the learning rate  and exploration factor decrease linearly as the number of episodes increases (for instance, eta[i] contains the learning rate for episode i).

Important: The ϵ-greedy policy based on Q should break ties randomly between actions that maximize Q for a given state. This plays a large role in encouraging exploration.

4    Non-tabular model-free reinforcement learning

In this task, you will treat the frozen lake environment as if it required linear action-value function approxi- mation.  Your task is to implement Sarsa control and Q-learning control using linear function approximation. In the process, you will learn that tabular model-free reinforcement learning is a special case of non-tabular model-free reinforcement learning. You may follow the interface suggested in Listing 4.

Listing 4: Non-tabular model-free algorithms.                                                    

class   LinearWrapper :

def       in it     ( self  ,   env ) :

self . env  =  env

self . n   actions  =  self . env . n   actions

self . n   states  =  self . env . n   states

self . n   features  =  self . n   actions   *   self . n   states

def  encode   state ( self  ,   s ) :

features  =  np . zeros (( self . n  actions ,   self . n  features ))

for   a   in  range( self . n   actions ) :

i  =  np . ravel  multi  index (( s ,   a ) ,   ( self . n  states  ,   self . n  actions )) features [ a ,   i ]  =  1.0

return   features

def  decode   policy ( self  ,   theta ) :

policy  =  np . zeros ( self . env . n  states  ,   dtype=int )

value  =  np . zeros ( self . env . n  states )

for   s   in  range( self . n   states ) :

features  =  self . encode  state ( s )

q  =  features . dot ( theta )

policy [ s ]  =  np . argmax(q)

value [ s ]  =  np . max(q)

return   policy ,   value

def  reset ( self ) :

return   self . encode  state ( self . env . reset ())

def  step ( self  ,   action ) :

state ,   reward ,   done  =  self . env . step ( action )

return   self . encode   state ( state ) ,   reward ,   done

def  render ( self  ,   policy=None ,   value=None ) :

self . env . render ( policy ,   value )

def   linear   sars a (env ,   max   episodes ,   eta ,  gamma,   epsilon  ,   seed=None ) :

random  state  =  np . random . RandomState( seed )

eta  =  np . linspace ( eta ,   0 ,   max  episodes )

epsilon  =  np . linspace ( epsilon  ,   0 ,   max  episodes )

theta  =  np . zeros ( env . n  features )

for   i   in  range( max   episodes ) :

features  =  env . reset ()

q  =  features . dot ( theta )

#  TODO:

return   theta

def   linear   q   learning (env ,   max   episodes ,   eta ,  gamma,   epsilon  ,   seed=None ) : random  state  =  np . random . RandomState( seed )

eta  =  np . linspace ( eta ,   0 ,   max  episodes )

epsilon  =  np . linspace ( epsilon  ,   0 ,   max  episodes )

theta  =  np . zeros ( env . n  features )

for   i   in  range( max   episodes ) :

features  =  env . reset ()

#  TODO:

return   theta

The class LinearWrapper implements a wrapper that behaves similarly to an environment that is given to its constructor. However, the methods reset  and step return a feature matrix when they would typically return a state s.  The a-th row of this feature matrix contains the feature vector  φ(s,a) that represents the pair of action and state (s,a).  The method encode  state is responsible for representing a state by such a feature matrix . More concretely, each possible pair of state and action is represented by a different vector where all elements except one are zero.  Therefore, the feature matrix has  |S||A|  columns.  The method  decode policy  receives a parameter vector θ obtained by a non-tabular reinforcement learning algorithm and returns the corresponding greedy policy together with its value function estimate.

The function linear sarsa  receives an environment  (wrapped by LinearWrapper), a maximum number of episodes, an initial  learning rate, a discount factor, an initial  exploration factor, and an (optional) seed that controls the pseudorandom number generator.  Note that the learning rate and exploration factor decay linearly as the number of episodes grows (for instance, eta[i]  contains the learning rate for episode i).