\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 24: Same Objective, Different Noise}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}
\maketitle

\subsection*{Submission Instructions}
Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 24: Same Objective, Different Noise \hfill \textnormal{2 points}}

A two-armed bandit chooses arm $1$ with probability $p=\sigma(\theta)$ and arm $0$ otherwise. The arms initially pay deterministic rewards $r_1$ and $r_0$. A teammate says that adding the same constant $c$ to both rewards is irrelevant because it does not change which policy is optimal.

Decide whether ``irrelevant'' is correct for one-sample REINFORCE training. Derive the exact objective gradient and the complete distribution of the one-sample estimator after the reward shift. Find the value of $c$ that minimizes its variance for a general $p\in(0,1)$, and determine whether zero variance is possible without making the true gradient zero.

Then replace each arm's deterministic reward by an independent draw with the same mean as before and conditional variance $s_a^2$ on arm $a$. Determine the best constant shift again and identify the part of the estimator variance that no constant can remove. Use the result to state precisely which aspects of the learning problem are unchanged by a reward shift and which are not.

\paragraph{Results you may use.}
For this Bernoulli policy, $\partial_\theta\log\pi_\theta(a)=a-p$. You may use the law of total variance.

%\input{solutions/solution24}
\end{document}
