\documentclass[10pt,letterpaper]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\title{
        CS444 HW \#9
}
\author{}
\date{}


\begin{document}
\newcommand{\bq}{\item \begin{samepage} }
\newcommand{\eq}{\end{samepage}}
\newcolumntype{C}{>{\centering\arraybackslash}p{.3in}}
\maketitle

Solutions to this assignment should be submitted through Blackboard as
.pdf files.

\begin{enumerate}

\bq Consider the MDP represented by the following simple maze:

\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
.75 & & &   & & & & & & 1.0  \\
\hline
\end{tabular}

The robot in this maze starts at location S.  At each time step he has the option of taking one of two actions LEFT, or RIGHT.  These actions deterministically move the robot one space to the left or right.  When the robot is in state A, he receives a reward of 0.75.  When he is in state B he receives a reward of 1.0.   Any action taken in states A or B end the trial: the robot exits the maze and no more steps are taken.  Assume a discount factor of $\gamma = .9$. As a reminder, here is the equation for the utility of a state under the optimal policy in an MDP:

\[ U(s) = R(s) + \gamma \max_a \sum_{s'} P(s' | s, a) U(s') \]



\begin{itemize}
\item In each square of the maze, write the utility (expected
  discounted reward under the optimal policy) of being in that state.
  States A and B are already completed.  (1pt)

\item In each square of the maze (other than A and B) indicate the
  optimal action for the robot to take.

\end{itemize}
\eq


\bq Fill out the following tables with the appropriate Q-values for
each action in each state.  Assume the same reward function and
transition model as the previous question.  As a reminder, the constraint equation for Q-values is:

\[ Q(s,a) = R(s) + \gamma \sum_{s'}P(s' | s, a) \max_{a'}  Q(s', a') \]

\small{
\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
.75$|$.75 &$|$ &$|$ & $|$  & $|$&$|$ & $|$& $|$&$|$ & 1.0$|$1.0 \\
\hline
\end{tabular}
}
\eq

\bq For this question, assume that we are using Q-learning to find a
policy for the environment described in Question 1. Assume a learning
rate of $\alpha=.1$.  All Q-values are initialized to 0:

\small{
\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
$0|0$ &$0|0$ & $0|0$ & $0|0$  & $0|0$&$0|0$ & $0|0$& $0|0$&$0|0$ & $0|0$ \\
\hline
\end{tabular}
}

As a reminder, the update equation for Q-learning is:

\[Q(s,a) \leftarrow Q(s,a) + \alpha (R(s) + \gamma \max_{a'} Q(s', a') - Q(s, a))\]

\begin{itemize}

\item  In the first trial, the agent randomly follows the following action sequence (starting from S): 

$\langle$LEFT, RIGHT, LEFT, LEFT, LEFT, LEFT$\rangle$

What are the estimated Q-values after this trial? 

\small{
\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
$|$ &$|$ & $|$ & $|$  & $|$&$|$ & $|$& $|$&$|$ & $|$ \\
\hline
\end{tabular}
}

\item  In the second trial, the agent randomly follows the following action sequence (starting from S): 

$\langle$LEFT, LEFT, LEFT, LEFT$\rangle$

What are the estimated Q-values after this trial? 

\small{
\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
$|$ &$|$ & $|$ & $|$  & $|$&$|$ & $|$& $|$&$|$ & $|$ \\
\hline
\end{tabular}
}

\item  In the third trial, the agent randomly follows the following action sequence (starting from S): 

$\langle$LEFT, LEFT, RIGHT, RIGHT, RIGHT, RIGHT, RIGHT, RIGHT, RIGHT, RIGHT, RIGHT$\rangle$

What are the estimated Q-values after this trial? 

\small{
\begin{tabular}{|C|C|C|C|C|C|C|C|C|C|}
\hline
A   & & & S & & & & & & B  \\
$|$ &$|$ & $|$ & $|$  & $|$&$|$ & $|$& $|$&$|$ & $|$ \\
\hline
\end{tabular}
}


\end{itemize}

\eq

\bq  Consider the problem of using a genetic algorithm to search for an optimal
policy for the MDP described above. 
\begin{itemize}
\item How could you encode policies for this problem as bit-strings?  Be specific.  How many bits does your encoding take?  

\item Describe an appropriate fitness function for this problem. 
\end{itemize}
\eq 


\end{enumerate}

\end{document}
