[Solved] CS 489 Assignment 1

Reinforcement Learning

1 Introduction

The goal of this assignment is to do experiment with Dynamic Programming(DP), including iterative policy evaluation, policy iteration and value iteration. Your goal is to implement DP methods and test them in the small gridworld mentioned in the slides of Lecture 3.

2 Small Gridworld

Figure 1: Gridworld

As shown in Fig.1, each grid in the Gridworld represents a certain state. Let st denotes the state at grid t. Hence the state space can be denoted as S = {st|t 0, .., 35}. S1 and _S35 are terminal states, where the others are non-terminal states and can move one grid to north, east, south and west. Hence the action space is A = {n, e, s, w}. Note that actions leading out of the Gridworld leave state unchanged. Each movement get a reward of -1 until the terminal state is reached.

A good policy should be able to find the shortest way to the terminal state randomly given an initial non-terminal state.

3 Experiment Requirments

• Programming language: python3
• You should build the Gridworld environment and implement iterative policy evaluation methods and policy iteration methods. Then run the two methods to evaluate and improve an uniform random policy (n|) = (e|) = (s|) = (w|) = 0.25