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

\title{CSCI 145 Problem 25: Audit Batch Centering}
\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 25: Audit Batch Centering \hfill \textnormal{2 points}}

Let $(G_i,\mathbf{u}_i)$ be $N$ independent trajectory samples, where $\mathbf{u}_i=\nabla_{\boldsymbol\theta}\log\pi_{\boldsymbol\theta}(\tau_i)$, $\mathbb E[\mathbf{u}_i]=\mathbf{0}$, and the desired policy gradient is $\mathbf{g}=\mathbb E[G_i \mathbf{u}_i]$. An implementation uses the same batch to form $\bar G=N^{-1}\sum_jG_j$ and reports
$$
\hat{\mathbf{g}}_{\mathrm{center}}=\frac1N\sum_{i=1}^N(G_i-\bar G)\mathbf{u}_i.
$$
The code comment says ``subtracting any action-independent baseline is unbiased.'' Audit that comment. Compute $\mathbb E[\hat{\mathbf{g}}_{\mathrm{center}}]$ exactly, including the case $N=1$, and explain why the usual baseline proof does not apply without modification.

For $N\geq2$, repair the estimator without collecting more trajectories. Your repair must use, for each sample, only returns from the other samples to construct its baseline. Prove unbiasedness and find an exact algebraic relation between your estimator and $\hat{\mathbf{g}}_{\mathrm{center}}$.

\paragraph{Optional starred extension $(\star)$.}
This extension is not required for full credit. Translate the lesson to a learned state-dependent critic. Give a concrete data-leakage or action-dependence condition that invalidates the standard unbiasedness argument, then repair it by cross-fitting: split the trajectories into folds and evaluate each trajectory using a critic trained only on other folds.

\paragraph{Results you may use.}
You may use independence across trajectories and the score identity $\mathbb E[\mathbf{u}_i]=\mathbf{0}$.

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