

![0_image_0.png](0_image_0.png)

implement, which simplifies their analysis and theoretical comparison.  We focus on the following properties: the complexity of the dynamic-programming (value-iteration) updates:
the complexity of value functions each method uses; the ability of methods to bound the exact update; the convergence of value iteration with approximate update rules; and the control performance of related controllers. The results of the theoretical analysis are illustrated empirically on a problem from the agent-navigation domain. In addition, we use the agent navigation problem to illustrate and give some intuitions on other characteristics of methods with no theoretical underpinning. Thus, these results should not be generalized to other problems or used to rank different methods.

## Agent- Navigation  Problem

Maze20 is a maze-navigation problem with 20 states, six actions and eight observations. The maze (Figure 11) consists of 20 partially connected rooms (states) in which a robot operates and collects rewards. The robot can move in four directions (north, south, east and west) and can check for the presence of walls using its sensors. But, neither "move" actions nor sensor inputs are perfect, so that the robot can end up moving in unintended directions. The robot moves in an unintended direction with probability of 0.3 (0.15 for each of the neighboring directions).  A move into the wall keeps the robot in the same position. Investigative actions help the robot to navigate by activating sensor inputs. Two such investigative actions allow the robot to check inputs (presence of a wall) in the northsouth and east-west directions. Sensor accuracy in detecting walls is 0.75 for a two-wall case (e.g. both north and south wall), 0.8 for a one-wall case (north or south) and 0.89 for a no-wall case, with smaller probabilities for wrong perceptions.

The control objective is to maximize the expected discounted rewards with a discount factor of 0.9. A small reward is given for every action not leading to bumping into the wall
(4 points for a move and 2 points for an investigative action), and one large reward (150 points) is given for achieving the special target room (indicated by the circle in the figure) and recognizing it by performing one of the move actions. After doing that and collecting the reward, the robot is placed at random in a new start position.

Although the Maze20 problem is of only moderate complexity with regard to the size of state, action and observation spaces, its exact solution is beyond the reach of current exact methods. The exact methods tried on the problem include the Witness algorithm (Kaelbling et al., 1999), the incremental pruning algorithm (Cassandra et al., 1997) 13 and 13. Many thanks to Anthony Cassandra for running these algorithms.