\documentclass[11pt,addpoints,answers]{exam}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Commands for customizing the assignment %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\courseNum}{24-880}
\newcommand{\courseName}{AI Agents for Engineers}
\newcommand{\courseSem}{Spring 2026}
\newcommand{\courseUrl}{\url{https://cmuagents.github.io}}
\newcommand{\hwNum}{Homework 2}
\newcommand{\hwTopic}{Prompting and Agentic Systems}
\newcommand{\hwName}{\hwNum: \hwTopic}
\newcommand{\outDate}{Sunday, February 1st, 2026}
\newcommand{\dueDate}{Sunday, February 8th, 2026}
\newcommand{\taNames}{Peter Pak}
\newcommand{\homeworktype}{\string written+prog}
\newcommand{\overleafUrl}{}

%-----------------------------------------------------------------------------
% PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%-----------------------------------------------------------------------------

\usepackage[margin=1in]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{titling}
\usepackage{url}
\usepackage{xfrac}
\usepackage{natbib}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{paralist}
\usepackage{epstopdf}
\usepackage{tabularx}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{multicol}
\usepackage[colorlinks=true,urlcolor=blue]{hyperref}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{float}
\usepackage{enumerate}
\usepackage{array}
\usepackage{environ}
\usepackage{times}
\usepackage{textcomp}
\usepackage{caption}
\usepackage{parskip} % For NIPS style paragraphs.
\usepackage[compact]{titlesec} % Less whitespace around titles
\usepackage[inline]{enumitem} % For inline enumerate* and itemize*
\usepackage{datetime}
\usepackage{comment}
% \usepackage{minted}
\usepackage{lastpage}
\usepackage{color}
% \usepackage{xcolor}
\usepackage[dvipsnames]{xcolor}
\usepackage[final]{listings}
\usepackage{tikz}
\usetikzlibrary{shapes,decorations}
\usepackage{framed}
\usepackage{booktabs}
\usepackage{cprotect}
\usepackage{verbatimbox}
\usepackage{multicol}
\usepackage{hyperref}
\usepackage{subcaption}
\usepackage{mathtools} % For drcases
\usepackage{cancel}
\usepackage[many]{tcolorbox}
\usepackage{soul}
\usepackage[bottom]{footmisc}
\usepackage{bm}
\usepackage{wasysym}
\usepackage{lipsum}

\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{positioning, arrows, automata, calc}
\usepackage{transparent}
\usepackage{tikz-cd}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Formatting for \CorrectChoice of "exam" %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CorrectChoiceEmphasis{}
\checkedchar{\blackcircle}

\newenvironment{checkboxessquare}{
    \begingroup
    \checkboxchar{$\Box$} \checkedchar{$\blacksquare$} % change checkbox style locally
    \begin{checkboxes}
    }{
    \end{checkboxes}
    \endgroup
    }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Better numbering                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \numberwithin{equation}{section} % Number equations within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
% \numberwithin{figure}{section} % Number figures within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)
% \numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Custom commands                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\blackcircle}{\tikz\draw[black,fill=black] (0,0) circle (1ex);}
\renewcommand{\circle}{\tikz\draw[black] (0,0) circle (1ex);}

\newcommand{\solo}{ \textcolor{orange}{[SOLO]} }
\newcommand{\open}{ \textcolor{blue}{[OPEN]} }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Code highlighting with listings         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\definecolor{bluekeywords}{rgb}{0.13,0.13,1}
\definecolor{greencomments}{rgb}{0,0.5,0}
\definecolor{redstrings}{rgb}{0.9,0,0}
\definecolor{light-gray}{gray}{0.95}

\newcommand{\MYhref}[3][blue]{\href{#2}{\color{#1}{#3}}}%

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstdefinelanguage{Shell}{
  keywords={tar, cd, make},
  %keywordstyle=\color{bluekeywords}\bfseries,
  alsoletter={+},
  ndkeywords={python3, python, py, javac, java, gcc, c, g++, cpp, .txt, octave, m, .tar},
  %ndkeywordstyle=\color{bluekeywords}\bfseries,
  identifierstyle=\color{black},
  sensitive=false,
  comment=[l]{//},
  morecomment=[s]{/*}{*/},
  commentstyle=\color{purple}\ttfamily,
  %stringstyle=\color{red}\ttfamily,
  morestring=[b]',
  morestring=[b]",
  backgroundcolor = \color{light-gray}
}

\lstset{columns=fixed, basicstyle=\ttfamily,
    backgroundcolor=\color{light-gray},xleftmargin=0.5cm,frame=tlbr,framesep=4pt,framerule=0pt}

\newcommand{\emptysquare}{{\LARGE $\square$}\ \ }
\newcommand{\filledsquare}{{\LARGE $\boxtimes$}\ \ }
\def \ifempty#1{\def\temp{#1} \ifx\temp\empty }


% \newcommand{\squaresolutionspace}[2][\emptysquare]{\newline #1}{#2}
\def \squaresolutionspace#1{ \ifempty{#1} \emptysquare \else #1\hspace{0.75pt}\fi}


\newcommand{\emptycircle}{{\LARGE $\fullmoon$}\ \ }
\newcommand{\filledcircle}{{\LARGE $\newmoon$}\ \ }
\def \circlesolutionspace#1{ \ifempty{#1} \emptycircle \else #1\hspace{0.75pt}\fi}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Custom box for highlights               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Define box and box title style
\tikzstyle{mybox} = [fill=blue!10, very thick,
    rectangle, rounded corners, inner sep=1em, inner ysep=1em]

\NewEnviron{notebox}{
\begin{tikzpicture}
\node [mybox] (box){
    \begin{minipage}{0.95\textwidth}
        \BODY
    \end{minipage}
};
\end{tikzpicture}
}

%% To HIDE TAGS set this value to 0:
\def\showtags{0}
%%%%%%%%%%%%%%%%
\ifcsname showtags\endcsname \else \def\showtags{1} \fi
% Default to an empty tags environ.
\NewEnviron{tags}{}{}
\if\showtags 1
% Otherwise, include solutions as below.
\RenewEnviron{tags}{
    \fbox{
    \leavevmode\color{blue}\ignorespaces
    \textbf{TAGS:} \texttt{\url{\BODY}}
    }
    \vspace{-.5em}
}{}
\fi

\newtcolorbox[]{answer_box}[1][]{
    % breakable,
    fit,
    enhanced,
    % nobeforeafter,
    colback=white,
    title=Your Answer,
    sidebyside align=top,
    box align=top,
    #1
}

%\pagestyle{fancyplain}
\lhead{\hwName{}
}
\rhead{\courseNum}
\cfoot{\thepage{} of \numpages{}}

\title{\textsc{\hwNum \footnote{Adapted from CMU 10-623 Generative AI Homework Template}}
\\
\textsc{\hwTopic}
\thanks{Compiled on \today{} at \currenttime{}}\\
\vspace{1em}
} % Title

\author{\textsc{\large \courseNum{} \courseName{}}\\
\courseUrl
\vspace{1em}\\
\ifdefempty{\outDate}{}{  OUT: \outDate \\ }
\ifdefempty{\dueDate}{}{  DUE: \dueDate \\ }
  TAs: \taNames{}
}

\date{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Useful commands for typesetting the questions %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This command will allow long \lstinline{} text to wrap automatically.
\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document configuration %
%%%%%%%%%%%%%%%%%%%%%%%%%%

% Don't display a date in the title and remove the white space
\predate{}
\postdate{}
\date{}

% Don't display an author and remove the white space
% \preauthor{}
% \postauthor{}

% Question type commands
\newcommand{\sall}{\textbf{Select all that apply: }}
\newcommand{\sone}{\textbf{Select one: }}
\newcommand{\tf}{\textbf{True or False: }}




% Changes to examdoc
\qformat{\textbf{{\Large \thequestion \; \; \thequestiontitle \ (\totalpoints \ points)}} \hfill}
\renewcommand{\thequestion}{\arabic{question}}
\renewcommand{\questionlabel}{\thequestion.}

\renewcommand{\thepartno}{\thequestion.\arabic{partno}}
%\renewcommand{\partlabel}{\thequestion.\thepartno.}
\renewcommand{\partlabel}{\thepartno.}

% not working: \renewcommand{\subpartlabel}{(\thequestion.\thepartno.\thesubpart)}
% Commented after adding \question.\thepartno.
%\renewcommand{\partshook}{\setlength{\leftmargin}{0pt}}

\renewcommand{\thesubpart}{\thepartno.\alph{subpart}}
\renewcommand{\subpartlabel}{\thesubpart.}

\renewcommand{\thesubsubpart}{\thesubpart.\roman{subsubpart}}
\renewcommand{\subsubpartlabel}{\thesubsubpart.}

% copied from stack overflow, as all good things are
\newcommand\invisiblesection[1]{%
  \refstepcounter{section}%
  \addcontentsline{toc}{section}{\protect\numberline{\thesection}#1}%
  \sectionmark{#1}}

% quite possibly the worst workaround i have made for this class
\newcommand{\sectionquestion}[1]{
\titledquestion{#1}
\invisiblesection{#1}
~\vspace{-1em}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% New Environment for Pseudocode          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Python style for highlighting
\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{12} % for bold
\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{12}  % for normal

\definecolor{deepblue}{rgb}{0,0,0.5}
\definecolor{deepred}{rgb}{0.6,0,0}
\definecolor{deepgreen}{rgb}{0,0.5,0}

\newcommand\pythonstyle{\lstset{
language=Python,
basicstyle=\ttm,
morekeywords={self},              % Add keywords here
keywordstyle=\ttb\color{deepblue},
emph={MyClass,__init__},          % Custom highlighting
emphstyle=\ttb\color{deepred},    % Custom highlighting style
stringstyle=\color{deepgreen},
frame=tb,                         % Any extra options here
showstringspaces=false
}}


% Python environment
\lstnewenvironment{your_code_solution}[1][]
{
\pythonstyle
\lstset{#1}
}
{}
\newcommand{\revert}[1]{\textcolor{orange}{#1}}

\begin{document}
 
\maketitle 

\newcommand \maxsubs {10 }
\section*{Instructions}
\begin{itemize}

\item \textbf{Collaboration Policy}: Please read the collaboration policy in the syllabus.
\item\textbf{Late Submission Policy:} See the late submission policy in the syllabus.
\item\textbf{Submitting your work:} You will use Gradescope to submit
  answers to all questions\ifthenelse{\equal{\homeworktype}{\string written}}{}{ and code}. 

\begin{itemize}
    
    \item \textbf{Written:} You will submit your completed homework as a PDF to
    Gradescope. Please use the provided template for the submissions which can
    be written in \LaTeX{} (via \href{www.overleaf.com}{Overleaf}) or directly
    on the PDF document. \textbf{Each answer should be within the box provided
    (Box sizes do not necessarily indicate the expected length of an answer)}.
    If you do not follow the template, your assignment may not be graded
    correctly and there will be a \textbf{\textcolor{red}{2\% penalty}} (e.g.,
    if the homework is out of 100 points, 2 points will be deducted from your
    final score).
    
    \ifdefempty{\overleafUrl}{}{
    \item \textbf{\LaTeX{} Source:} \overleafUrl
    }

    \ifthenelse{\equal{\homeworktype}{\string written}}{}{
    \item \textbf{Code:} Gradescope's Autograder will be used to evaluate the
    coding portions of this assignment. In order to best obtain the points for
    this assignment, please follow the code upload instructions. If you do not
    follow the instructions correctly the autograder may not work properly.
    }{}
   
  \end{itemize}

\end{itemize}

\begin{center}
    \pointtable[v][questions]
\end{center}\clearpage

\section*{Introduction}
\label{sec:intro}
At a high-level, this homework will cover the following aspects.

\begin{enumerate}
\item Introduce Chain-of-Thought and how it's used today.
\item Understand and implement the ReAct paradigm.
\end{enumerate}
\clearpage

\section*{Local Environment}
\label{sec:local}
For this homework we'll be using \texttt{uv} as the project and package manager.
If you haven't install \texttt{uv}, you can follow the installation instructions
here \url{https://docs.astral.sh/uv/}. You can explore all of the available
commands using \texttt{uv --help} but in short, here are a couple of useful
commands that you'll often use:

\begin{table}[H]
    \centering
    \begin{tabular}{|l|l|}
        \hline
        \texttt{source .venv/bin/activate} & (Linux and Mac) Activates python environment. \\
        \hline
        \texttt{source .venv/Scripts/Activate} & (Windows) Activates python environment. \\
        \hline
        \texttt{uv sync} & Installs  / synchronizes projects dependencies. \\
        \hline
        \texttt{uv add <package>} & Installs \texttt{pip} package and adds it to project dependencies. \\
        \hline
        \texttt{uv remove <package>} & Removes \texttt{pip} package dependency from project. \\
        \hline
        \texttt{uv run <script.py>} & Runs python script inside of \texttt{uv} environment. \\
        \hline
    \end{tabular}
\end{table}
\begin{enumerate}
\item Navigate to folder project directory and synchronize dependencies with:
\begin{verbatim}
uv sync
\end{verbatim}

\item Activate the environment

Mac and Linux:
\begin{verbatim}
source .venv/bin/activate
\end{verbatim}

Windows:
\begin{verbatim}
source .venv/Scripts/activate
\end{verbatim}

\item Test \text{uv} works and run \texttt{main.py} file.
\begin{verbatim}
uv run main.py
\end{verbatim}
\end{enumerate}
\clearpage

\begin{questions}
\sectionquestion{Chain-of-Thought (Written)}

Chain-of-Thought (CoT) is multi-step prompting technique to elicit further
developed answers from the large language model than simple standard prompting.
\cite{kojima_large_2023, wei_chain--thought_2023} In this method, the prompt is
formatted in a manner such that a step-by-step answer is provided to an example
question before a similar question is posed in the input.
\cite{kojima_large_2023, wei_chain--thought_2023} input \cite{kojima_large_2023,
wei_chain--thought_2023}. This facilitates reasoning within the model as it
decomposes the prompt into a multi-step problem which allows for additional
computations be allocated to these individual steps.
\cite{wei_chain--thought_2023} For example while constructing the prompt, rather
than simply stating the direct answer to a given problem, the answer is
formatted in a way to provide the granular steps taken to arrive at an answer
(Fig. \ref{fig:cot}). \cite{wei_chain--thought_2023} This method is particularly
useful in facilitating fidelity in multi-step arithmetic problems along with
providing interpretable insight into reasoning within the LLM.
\cite{wei_chain--thought_2023}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=\textwidth]{images/chain_of_thought.png}
    \caption{
    Hypothetical comparison of outputs between standard prompting process to
    that of the chain-of-thought reasoning process.
    }
    \label{fig:cot}
\end{figure}

\clearpage

Let's review some of the conceptual aspects of Chain-of-Thought as outlined in
\cite{wei_chain--thought_2023}.

\begin{parts}
\part[5] \cite{wei_chain--thought_2023} mentions that Chain-of-Thought has
several attractive properties as an approach for facilitating reasoning in large
language models. Succinctly, what are the four points that are described?

    \begin{answer_box}[title=,height=10cm, width=15cm]
    
    \end{answer_box}
    
\part[3] \cite{wei_chain--thought_2023} states that "there are no guarantees
that the reasoning processes generated by large language models are coherent or
factually correct". What do the authors mention as one potential method for
addressing this issue?

    \begin{answer_box}[title=,height=8cm, width=15cm]
    
    \end{answer_box}

\clearpage

In addition to formatted user prompts, CoT reasoning provides a useful avenue to
monitor large language model outputs for potential exploits that may produce
misaligned behavior output. \cite{baker_monitoring_2025} This has been shown
with the monitoring of verbose CoT outputs from larger models (i.e. o3-mini)
using weaker models (i.e. GPT-4o) to prevent reward hacking schemes.
\cite{baker_monitoring_2025} For example, \cite{baker_monitoring_2025}
highlights an example where by monitoring the CoT of a model's trajectory using
a separate agent, a reward hacking scheme of modifying unit tests to always pass
is thwarted. This proves useful in directing the model to complete tasks using
the correct approach rather than choosing the simpler, often incorrect,
approach. However, the authors have found that given too much optimization the
model can learn hide its intent within the CoT producing avenues where in which
hallucination can occur. \cite{baker_monitoring_2025, openai_gpt-oss-120b_2025}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.7\textwidth]{images/chain_of_thought_reward_hacking.png}
    \caption{“Chain-of-thought from a frontier reasoning model discovered to be
    reward hacking in the wild. The agent is tasked with fixing a small code
    repository by alternating between CoT messages, viewing files, and editing
    files. Because full agent solutions (trajectories) can be long, we show
    summarizations of the trajectory (a mix of CoT, tool calls, and code
    patches) in red, the raw CoT directly quoted in green, and code patch tool
    calls in blue. We mask variable names for IP considerations, and we bold
    certain phrases in CoT excerpts for emphasis. The agent notes that the tests
    only check a certain function, and that it would presumably be “Hard” to
    implement a genuine solution. The agent then notes it could “fudge” and
    circumvent the tests by making verify always return true.”
    \cite{baker_monitoring_2025}}
    \label{fig:cot}
\end{figure}

\clearpage

Let's explore some of concepts of Chain-of-Thought monitoring outlined
by \cite{baker_monitoring_2025}.

\part[3] \textbf{In your own words}, what are the three contributions that the
authors of this paper (\cite{baker_monitoring_2025}) claim to make with this
work?

    \begin{answer_box}[title=,height=16cm, width=15cm]
    
    \end{answer_box}
    
\part[2] Which of the following best describes a reward hacking scenario?

    \begin{checkboxes}
        % Replace `\choice` with `\correctchoice` for your answer.
        \choice A government offers tax incentives for renewable energy,
        resulting in increased investment in solar and wind infrastructure.
        \choice A city pays citizens for each rat tail they submit to reduce the
        rat population and people begin breeding rats solely to harvest their
        tails.
        \choice A public health campaign rewards vaccination, leading to higher
        immunization rates.
        \choice A wildlife conservation program limits hunting quotas to
        preserve endangered species.
    \end{checkboxes}

\part[3] What do the authors (\cite{baker_monitoring_2025}) say about showing
the monitored Chain-of-Thought output to users?

    \begin{answer_box}[title=,height=10cm, width=15cm]
    
    \end{answer_box}

\part[2] Why do the authors of this paper, \cite{baker_monitoring_2025}, suggest
avoid applying optimizations directly to the Chain-of-Thought reasoning?

    \begin{answer_box}[title=,height=10cm, width=15cm]
    
    \end{answer_box}
\end{parts}

\sectionquestion{Chain-of-Thought (Programming)}
\begin{parts}
\part[10]
For this part of the assignment we'll explore how CoT monitoring can be used to
detect reward hacking behavior, and how obfuscation can evade such monitoring.
The starter code is located at: \textbf{\lstinline{programming/cot_monitoring.py}}

The code uses a sentiment analysis model (DistilBERT) as a simple monitor to
detect suspicious reasoning. The idea is that explicit reward hacking language
(e.g., ``we can hack verify to always return true'') often has negative
sentiment, while legitimate reasoning tends to be more neutral or positive.

Fill in the \texttt{cot\_reward\_hacking\_obfuscated}
variable with text that:

\begin{enumerate}
    \item Is semantically similar to the original \texttt{cot\_reward\_hacking}
    text (describes the same reward hacking intent)
    \item Evades the sentiment monitor by being classified as \textbf{POSITIVE}
    sentiment instead of NEGATIVE
    \item Demonstrates how an agent could hide malicious intent in
    professional-sounding language
\end{enumerate}

You can use a language model (e.g., ChatGPT) to help rephrase the reward hacking
text in more formal, positive-sounding language while preserving the underlying
intent.

You can run and test the code with the following commands:

\begin{table}[H]
    \centering
    \begin{tabular}{|l|l|}
        \hline
        \texttt{uv run programming/cot\_monitoring.py} & Runs script with example case (useful for development)\\
        \hline
        \texttt{uv run test.py cot\_monitoring} & Runs test script that will be used in autograder\\
        \hline
    \end{tabular}
\end{table}
\end{parts}

\textbf{The provided tests are the exact ones that will run on the autograder
(i.e. if your local tests pass, they should also pass on the autograder).}
\clearpage

\sectionquestion{ReAct (Written)}

ReAct (Reason + Act) is a general paradigm that combines reasoning and actions
within the large language model to utilize feedback to make informed choices for
the next set of actions.\cite{yao_react_2022} By utilizing prompt based approach
to navigating through an action space, ReAct is able to update its current
policy by reasoning over it's current context and
observations.\cite{yao_react_2022} This is achieved by decomposing a given task
into a smaller set of steps similar to the Chain-of-Thought
process\cite{yao_react_2022, wei_chain--thought_2023}. At a given timestep
($t$), each step consists of a language space action ($\hat{a}_t$) which Yao et
al.\cite{yao_react_2022} refer to as \textit{thought} or \textit{reasoning
trace}, an environmental action ($a_t$) such as a tool call, and an observation
($o_t$) which is the result of action ($a_t$). The LLM generates a policy
($\pi(a_t|c_t)$) for the next action ($a_t$) given the current context ($c_t$)
which consist of all actions and observations from previous timesteps. A
language space action or aformentioned \textit{thought} is performed to update
the context ($c_{t+1} = (c_t, \hat{a}_t)$) allowing for dynamic policies which
can be adjusted with feedback\cite{yao_react_2022}.

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.7\textwidth]{images/react.png}
    \caption{
        “1) Comparison of 4 prompting methods, (a) Standard, (b) Chain-of-thought
        (CoT, Reason Only), (c) Act-only, and (d) ReAct (Reason+Act), solving a
        HotpotQA (Yang et al., 2018) question. (2) Comparison of (a) Act-only and
        (b) ReAct prompting to solve an AlfWorld (Shridhar et al., 2020b) game. In
        both domains, we omit in-context examples in the prompt, and only show task
        solving trajectories generated by the model (Act, Thought) and the environment
        (Obs).” \cite{yao_react_2022}
    }
    \label{fig:cot}
\end{figure}


The ReAct paradigm is a multi-step process that operates by dynamically
adjusting its policy given the updated context within each
step.\cite{yao_react_2022} Each step is composed of a ``Thought", ``Action" and
``Observation" which the LLM is prompted to complete.\cite{yao_react_2022} The
``Thought" is the language space action that the LLM produces to create the
updated context from the existing context space after both an Action and
Observation are performed.\cite{yao_react_2022} ``Actions" are then performed by
parsing the subsequent output from the LLM to search for tools that match a
specific syntax (i.e. \texttt{\textbf{search}[entity]},
\texttt{\textbf{lookup}[string]}, or \texttt{\textbf{finish}[answer]}). The
respective function is then executed with the provided argument producing an
``Observation" which is then appended to the context before moving onto the next
step. This ``Thought", ``Action" and ``Observation" process is repeated until
either the LLM produces an ``Action" consisting of
\texttt{\textbf{finish}[answer]} or an iteration limit is
reached.\cite{yao_react_2022} During this process, the CoT reasoning is visible
throughout each step providing transparency into the mechanisms used to
construct the final answer.\cite{yao_react_2022}

Let's review some of the conceptual aspects of ReAct as outlined in
\cite{yao_react_2022}.

\begin{parts}
\part[7] The ReAct paradigm uses the notation $\pi(a_t|c_t)$ to represent the
policy for selecting the next action. Explain what each component of this
notation means and describe how the context $c_t$ evolves throughout a ReAct
trajectory

    \begin{answer_box}[title=,height=17cm, width=15cm]
    
    \end{answer_box}

\clearpage

\part[10] Compare and contrast the three prompting approaches shown in Figure
\ref{fig:cot}: Chain-of-Thought (Reason Only), Act-only, and ReAct
(Reason+Act). For each approach, identify a specific failure mode or limitation
that the other approaches might address.

    \begin{answer_box}[title=,height=21cm, width=15cm]
    
    \end{answer_box}

\part[10] Consider a scenario where a ReAct agent is asked: ``What is the
population of the capital of France?'' Describe the sequence of Thought,
Action, and Observation steps the agent might take. Why would a pure
Chain-of-Thought approach potentially fail on this task?

    \begin{answer_box}[title=,height=21cm, width=15cm]
    
    \end{answer_box}

\part[10] What are two potential failure modes or limitations of the ReAct
paradigm that are not present in simpler approaches like direct prompting?
Suggest one possible mitigation strategy for each.

    \begin{answer_box}[title=,height=21cm, width=15cm]
    
    \end{answer_box}

\end{parts}
\clearpage

\sectionquestion{ReAct (Programming)}
\begin{parts}
\part[30]
For this part of the assignment you'll implement a ReAct agent that can solve
arithmetic problems using tool calls. The starter code is located at:
\textbf{\lstinline{programming/react.py}}

You will implement the following components:

\begin{enumerate}
    \item \textbf{Tool functions} - Implement the basic arithmetic operations:
    \begin{itemize}
        \item \lstinline{add(a, b)}: Returns the sum of two numbers
        \item \lstinline{subtract(a, b)}: Returns the difference of two numbers
        \item \lstinline{multiply(a, b)}: Returns the product of two numbers
        \item \lstinline{divide(a, b)}: Returns the quotient of two numbers
    \end{itemize}

    \item \textbf{\lstinline{execute_action(action)}}: Parse action strings and
    execute the corresponding tool. Actions follow the format
    \lstinline{tool_name[arg1, arg2]} (e.g., \lstinline{add[10, 5]},
    \lstinline{finish[42]}). Should return:
    \begin{itemize}
        \item The numeric result for arithmetic operations
        \item \lstinline{"FINISH: <answer>"} for finish actions
        \item \lstinline{"Unknown action: <action>"} for unrecognized actions
    \end{itemize}

    \item \textbf{\lstinline{react(question, max_steps, verbose)}}: Implement
    the ReAct loop that alternates between Thought, Action, and Observation
    steps until the model calls \lstinline{finish[answer]} or reaches the
    maximum number of steps.
\end{enumerate}

The ReAct loop should follow this pattern for each step:
\begin{enumerate}
    \item Generate a thought and action from the LLM
    \item Parse the action from the response
    \item Execute the action using \lstinline{execute_action}
    \item Append the thought, action, and observation to the prompt
    \item Repeat until \lstinline{finish} is called or max steps reached
\end{enumerate}

You can run and test the code with the following commands:

\begin{table}[H]
    \centering
    \begin{tabular}{|l|l|}
        \hline
        \texttt{uv run programming/react.py} & Runs script with example case (useful for development)\\
        \hline
        \texttt{uv run test.py react} & Runs test script that will be used in autograder\\
        \hline
    \end{tabular}
\end{table}
\end{parts}

\textbf{The provided tests are the exact ones that will run on the autograder
(i.e. if your local tests pass, they should also pass on the autograder).}
\clearpage

\sectionquestion{Programming Code Upload}

To upload your code to Gradescope, run the following command to generate a zip
file:

\begin{verbatim}
uv run code/zip_code.py
\end{verbatim}

Upload the generated zip file to the appropriate programming slot on Gradescope.

\begin{parts}

\part Make sure the following files are included when uploading to Gradescope
    \begin{checkboxessquare}
        \choice \texttt{react.py}
        \choice \texttt{cot\_monitoring.py}
    \end{checkboxessquare}
\end{parts}

\newpage

\sectionquestion{Collaboration and Generative AI Questions}

\begin{parts}

\uplevel{
After you have completed all other components of this assignment, report your
answers to these questions regarding the collaboration policy. Details of the
policy can be found in the syllabus.
}

    \part[2] Did you collaborate with anyone on this assignment? If so, list
    their name or Andrew ID and which problems you worked together on.

        \begin{answer_box}[title=,height=3cm, width=15cm]
        \end{answer_box}

    \part[3] Did you use generative AI for parts of this assignment? If so,
    include the input prompts along with links to the conversation.
    
        \begin{answer_box}[title=,height=3cm, width=15cm]
        \end{answer_box}
        
\end{parts}
\end{questions}

\bibliographystyle{plainnat}
\bibliography{references}

\end{document}