\documentclass[11pt]{article}

% -------------------------------------------------
% Packages
% -------------------------------------------------
\usepackage[margin=1in]{geometry}          % Page geometry
\usepackage{xcolor}                        % Color definitions

% Math & Fonts
\usepackage{amsmath,amssymb,amsthm}        % AMS math
\usepackage{fontawesome5}                  % Icons
\usepackage{minted}                        % Code listings

% Graphics
\usepackage{graphicx}                      % Include graphics

% Lists and boxes
\usepackage{enumitem}                      % Customisable lists
\usepackage[most]{tcolorbox}               % Colored boxes

% Header / footer
\usepackage{fancyhdr}                      % Fancy header

% Hyperlinks (keep last)
\usepackage{hyperref}                      % Hyperlinks

% -------------------------------------------------
% Macros & Styles
% -------------------------------------------------

% Course‑specific info
\newcommand{\course}{ECE 531/COS 531: Robot Planning Meets Machine Learning}
\newcommand{\semester}{Fall 2025}
\newcommand{\hwNum}{0}
\newcommand{\dueDate}{September~8,~2025 at 11:59pm}

% Common icons
\newcommand{\WritingIcon}{\faEdit}
\newcommand{\CodeIcon}{\faLaptopCode}
\newcommand{\WarningIcon}{\faExclamationTriangle}


% tcolorbox base style
\tcbset{
  base/.style={
    before skip=2em,
    after skip=2em,
    colback=purple!5!white,
    colframe=purple!25!white,
    fonttitle=\bfseries,
    coltitle=black,
    boxrule=0.8pt,
    arc=4pt,
    left=6pt,right=6pt,top=6pt,bottom=6pt
  }
}

% Individual box styles
\newtcolorbox{instructionsbox}[1][]{base,title=Instructions,#1}
\newtcolorbox{ponderbox}[1][]{base,title=Pause to Ponder (No Points \& No Submission Required),#1}
\newtcolorbox{warningbox}[1][]{base,title=\WarningIcon\ Important Note,#1}

% Answer box macro
\newcommand{\AnswerBox}[1]{\framebox[\textwidth][c]{\rule{0pt}{#1}}}

% Spacing
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}

% Header / footer
\pagestyle{fancy}
\fancyhf{}
\lhead{\course}
\rhead{\semester}
\cfoot{\thepage}

% Hyperref colors
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    urlcolor=blue,
    citecolor=blue,
}

% Title
\title{\vspace{-3em}\textbf{Homework \hwNum}\vspace{-2em}}
\date{\vspace{-1em}Due: \dueDate\vspace{-2em}}

% -------------------------------------------------
\begin{document}
\maketitle
\thispagestyle{fancy}

\begin{instructionsbox}
\begin{itemize}
    \item See \url{https://rpmml.github.io/homework_instructions/} for instructions on accessing the accompanying code and submitting homework via GradeScope.
    \item See \url{https://rpmml.github.io/policies} for additional policies regarding collaboration, LLMs, and late submissions.
    \item Use Piazza or attend office hours to ask questions about the homework.
\end{itemize}
\end{instructionsbox}

\section*{Part 1: Written Exercises}

For the first two questions in this homework, consider the following MDP:
\begin{itemize}
    \item The state space is $\mathcal{S} = \{\texttt{hot}, \texttt{neutral}, \texttt{cold}\}$.
    \item The action space is $\mathcal{A} = \{\texttt{heat}, \texttt{cool}\}$.
    \item The reward function is
\[
  R(s, a, s') =
  \begin{cases}
      -1 & s = \texttt{hot}\\
      \;\;0 & s = \texttt{neutral}\\
      -2 & s = \texttt{cold}
  \end{cases}
\]
    \item The transition distribution is
\[
\begin{array}{c|c|c|c|c}
s & a & P(\texttt{hot}) & P(\texttt{neutral}) & P(\texttt{cold}) \\ \hline
\texttt{hot}     & \texttt{cool} & 0.2 & 0.7 & 0.1 \\
\texttt{hot}     & \texttt{heat} & 0.9 & 0.1 & 0.0 \\
\texttt{neutral} & \texttt{cool} & 0.1 & 0.3 & 0.6 \\
\texttt{neutral} & \texttt{heat} & 0.6 & 0.3 & 0.1 \\
\texttt{cold}    & \texttt{cool} & 0.0 & 0.2 & 0.8 \\
\texttt{cold}    & \texttt{heat} & 0.2 & 0.6 & 0.2 \\
\end{array}
\]
    \item The horizon is infinite.
    \item The temporal discount factor is $\gamma = 0.9$.
\end{itemize}

\subsection*{\WritingIcon\ Practice with Policy Evaluation (15 points)}
Consider the policy
\[
\pi(s)=
\begin{cases}
  \texttt{cool} & s = \texttt{hot}\\
  \texttt{heat} & s = \texttt{neutral}\\
  \texttt{heat} & s = \texttt{cold}
\end{cases}
\]

We wish to compute the value function for this policy $V^\pi: \mathcal{S} \to \mathbb{R}$.
Write a system of linear equations for $V^\pi$. You should simplify the expressions, but you do not need to solve the system.
Your equations should only contain the three variables $V^\pi(\texttt{hot}), V^\pi(\texttt{neutral})$, and $V^\pi(\texttt{cold})$, which you should abbreviate $h$, $n$, and $c$ respectively.

% \AnswerBox{5cm}

\begin{ponderbox}
Is it possible to construct an MDP and a policy that leads to a non-invertible linear system?
\end{ponderbox}

\subsection*{\WritingIcon\ Practice with Value Iteration (15 points)}

Show the first two iterations of value iteration by filling in the table below. You can check your work with code, but you should do the computation by hand first to internalize the algorithm.
Show your work to receive partial credit.

\framebox[\textwidth][c]{
\rule{0pt}{20em}
$
\begin{array}{c|c|c|c}
\text{iteration}  & V^*(\texttt{hot}) & V^*(\texttt{neutral}) & V^*(\texttt{cold}) \\ \hline
0 & 0.0 & 0.0 & 0.0 \\
1 &  &  &  \\
2 &  &  &  \\
\end{array}
$
}

\begin{ponderbox}
How does the initialization (all zeros in the example above) impact value iteration?
\end{ponderbox}

\subsection*{\WritingIcon\ Stretching the Definitions (10 points)}

Consider the following dialogue.

\emph{\textbf{Alex:} ``I read in a book that an MDP has a reward function $R(s)$. But I have invented a new model called AlexMDP, which is the same as an MDP, except that its reward function $R(s, a, s')$ is a function of the current state, action, and next state. I will develop new algorithms for AlexMDP that will make me rich and famous.''
}

\emph{\textbf{Blake:} ``I hate to burst your bubble, but AlexMDPs are basically the same as MDPs. In fact, I learned the $R(s, a, s')$ definition in my class.''}

\emph{\textbf{Alex:} ``No way! Prove they are the same.''}

\emph{\textbf{Blake:} ``Okay. I will write a program that efficiently converts any AlexMDP into an MDP. Then, I will run value iteration on that MDP to get an optimal policy. Finally, I will write another program that efficiently converts the MDP optimal policy into an optimal policy for the original AlexMDP.''}

\emph{\textbf{Alex:} ``I don't believe that's possible. Also, you can't go the other way.''}

Who will eventually win this argument? Explain your answer in 3-5 sentences.

% \AnswerBox{10cm}

\section*{Part 2: Coding Exercises}

\subsection*{\CodeIcon\ Coding Warm-Up (5 points)}

Complete the function \mintinline{python}{treats_are_sufficient} in \mintinline{python}{warmup.py}.
Examine the unit tests in \mintinline{python}{test_warmup.py} to make sure you understand the question.
No written answer required.

\subsection*{\CodeIcon\ Is Uncertainty Necessary? (20 points)}

In this exercise, you will explore the extent to which it is necessary to reason about uncertainty during MDP planning.
Your job is to implement \mintinline{python}{CustomMDP} in \mintinline{python}{uncertainty.py} so that when the transition distribution is \emph{determinized} (see \mintinline{python}{DeterminizedCustomMDP}), running value iteration leads to a grave mistake.
See \mintinline{python}{test_determinized_worse_than_custom_mdp}.
To keep things interesting, the rewards in your MDP must be bounded between $-1$ and $1$.
No written answer required.

\subsection*{\CodeIcon\ \WritingIcon\ Practice with Problem Formulation (30 points)}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/grid.pdf}
    \caption{Illustration of the home robot design problem.}
    \label{fig:home-robot}
\end{figure}

You have been hired as a consultant for a company that is developing a home robot.
The company is considering a home that already has a robot vacuum that could get in the way of their new robot.
This is a very difficult problem, but fortunately, the home and robot are rather simple (Figure~\ref{fig:home-robot}):
\begin{enumerate}
    \item The home is just a 2D grid with 5 rows and 15 columns.
    \item The vacuum only moves up and down in the middle column of the grid. Specifically, every minute, it moves up one cell with probability 0.25, down with probability 0.25, and stays in place with probability 0.5, except at the edges, where it stays in place with probability 0.75.
    \item The new home robot only moves left and right in the middle row of the grid. Its movement is deterministic---it can choose to move one cell left, or one right. It cannot stay still.
    \item The robot's job is done when it reaches the leftmost column.
    \item It costs \$0.1 to operate the robot for one minute. It costs $\$ 1000$ if the robot runs into the vacuum and breaks the robot permanently. 
    \item There is a 1\% chance that the user will permanently turn off the robot after every minute. This incurs no cost.
\end{enumerate}

Your job is to design an optimal policy for the robot.
However, the robot has limited sensors.
It cannot detect its exact position in the grid.
Instead, it can only sense:
\begin{itemize}
    \item The Manhattan distance between the home robot and the vacuum.
    \item Whether the home robot's current column is greater than, less than, or equal to the vacuum's (middle) column.
\end{itemize}

Design an optimal (in terms of \$ cost) policy that uses only these features, or show that this is impossible.
You should make your case either way with code, which you should submit, along with a written explanation (3-5 sentences).
You can use any code provided in the \mintinline{python}{rpmml} library or any of its dependencies (see \mintinline{python}{pyproject.toml}).

\begin{warningbox}
Submit your answer to this question in the \textbf{Written} assignment on Gradescope. Provide a link to your code that can be accessed by course instructors (e.g, use Google Drive).
\end{warningbox}

% \AnswerBox{10cm}

% \framebox[\textwidth][l]{
% \parbox{8cm}{%
% \vspace{0.1cm}
% \textbf{Code link:}
% \vspace{0.1cm}
% }%
% }

\section*{Part 3: Feedback}

\subsection*{\WritingIcon\ General Course Feedback (5 points)}

How can we improve the course in future years? Any and all feedback is welcome. Please comment on this problem set, lectures, and anything else.
Some feedback is required for full credit.
If you prefer to additionally submit anonymous feedback, please do so through the course website.

% \AnswerBox{6cm}

\end{document}
