\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{csquotes}
\usepackage{dsfont}
\usepackage{thmtools}
\usepackage{etoolbox}
\usepackage{enumitem}
\usepackage{fullpage}
\usepackage{parskip}
\usepackage{xcolor}
\usepackage{verbatim}

\usepackage[colorlinks,linkcolor=red!80!black]{hyperref}
\usepackage[noabbrev,capitalize]{cleveref}

\definecolor{question}{rgb}{0,0,1}
\crefname{section}{Question}{Questions}
\newlist{qlist}{enumerate}{1}

\newif\iffirstq
\firstqfalse
\setlist[qlist,1]{%
    leftmargin=*,
    label=\textbf{\color{black}[\thesection.\arabic*]}, ref={[\thesection.\arabic*]},
}
\crefname{qlisti}{Question}{Questions}
\AtBeginEnvironment{qlist}{\color{question}}

\definecolor{answer}{rgb}{0,.5,0}
\newcommand{\ans}[1]{\par\textcolor{answer}{Answer: #1}}
\newenvironment{answer}{\par\begingroup\color{answer}Answer: }{\endgroup}

\definecolor{points}{rgb}{0.6,0.3,0}
\newcommand{\pts}[1]{\textcolor{points}{[#1~points]}}

\newcommand{\hint}[1]{\textcolor{black!60!white}{\emph{Hint: #1}}}
\newcommand{\meta}[1]{\textcolor{black!60!white}{\emph{#1}}}

\newcommand{\TODO}{\textcolor{red}{TODO}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\DeclareMathOperator{\bigO}{\mathcal{O}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator{\ERM}{ERM}
\newcommand{\eps}{\varepsilon}
\newcommand{\indic}{\mathds{1}}
\newcommand{\Lip}{\mathrm{Lip}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Rad}{Rad}
\newcommand{\SG}{\mathcal{SG}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\Tr}{Tr}
\newcommand{\ud}{\mathrm{d}}
\DeclareMathOperator{\Unif}{Unif}
\DeclareMathOperator{\VCdim}{VCdim}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\xdist}{\mathcal{D}_x}
\DeclareMathOperator{\Bernoulli}{Bernoulli}
\DeclareMathOperator{\regret}{\mathcal{R}}

%%begin novalidate  % overleaf code check gives false positives here
\makeatletter
% \abs{} uses auto-sized bars, \abs*{} uses regular-sized ones
\newcommand{\abs}{\@ifstar{\@abs}{\@Abs}}
\newcommand{\@abs}[1]{\lvert #1 \rvert}
\newcommand{\@Abs}[1]{\left\lvert #1 \right\rvert}

\newcommand{\norm}{\@ifstar{\@norm}{\@Norm}}
\newcommand{\@norm}[1]{\lVert #1 \rVert}
\newcommand{\@Norm}[1]{\left\lVert #1 \right\rVert}

\newcommand{\ceil}{\@ifstar{\@ceil}{\@Ceil}}
\newcommand{\@ceil}[1]{\lceil #1 \rceil}
\newcommand{\@Ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\floor}{\@ifstar{\@floor}{\@Floor}}
\newcommand{\@floor}[1]{\lfloor #1 \rfloor}
\newcommand{\@Floor}[1]{\left\lfloor #1 \right\rfloor}
\makeatother
%%end novalidate

\numberwithin{equation}{section}
\declaretheorem[name=Theorem,numberwithin=section]{thm}
\declaretheorem[name=Proposition,sibling=thm]{prop}

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2024: Assignment 4
\\
due Friday, December 6 at 11:59pm
\end{center}

\vspace{2cm}


You can do this with a partner if you'd like (there's a ``find a group'' post on Piazza).
% Do assignment 1 alone; future ones will allow partners.
\textbf{Read the website section on academic integrity}
\href{https://www.cs.ubc.ca/~dsuth/532D/24w1/#policies}{here}
for what you're allowed to do and not do;
in particular, cite your sources (including people you talked to!)
and don't use ChatGPT/etc.
If you're not sure if something is okay, ask.

Prepare your answers to these questions using \LaTeX;
hopefully you're reasonably familiar with it,
but if not, try using Overleaf and looking around for tutorials online.
Feel free to ask questions if you get stuck on things on Piazza
(but remove any details about the actual answers to the questions\dots
make a private post if that's tough).
If you prefer, the \texttt{.tex} source for this file is available on the course website,
and you can put your answers in
\verb|\begin{answ|\verb|er} My answer here... \end{answer}|
% that weird formatting so my answer-stripping script doesn't catch it :p
environments to make them stand out;
feel free to delete whatever boilerplate you want.
Or answer in a fresh document.

Submit your answers as a single PDF on Gradescope:
\href{https://canvas.ubc.ca/courses/156968/external_tools/54329?display=borderless}{here's the link}.
Make sure to use the Gradescope group feature if you're working in a group.
You'll be prompted to mark where each question is in your PDF;
make sure you mark all relevant pages for each part (which saves us a surprising amount of grading time).

Please \textbf{put your name on the first page} as a backup, just in case.
If something goes wrong, you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage

\section{Highwaymen, robbers, and so forth \pts{55 + 5 challenge}}

We have an arm set $[K] = \{1, \dots, K\}$.
Rewards from pulling the $j$th arm are sampled from $\Bernoulli(\mu_j)$, independent of everything else.
Suppose there is a unique optimal arm $j^*$.
Define $\Delta_j = \mu_{j^*} - \mu_j$ to be the gap in mean reward of arm $j$.

We will run the following game protocol
for a sufficiently large number of rounds $T$
(in particular, $T \gg K$).

In each round $t =1, 2, \dotsc, T$,
\begin{enumerate}
    \item Nature decides upon a reward vector $X_t = \left(X_{1,t}, X_{2,t}, \ldots, X_{K, t} \right)$, by drawing each $X_{j,t} \sim \Bernoulli(\mu_j)$, independently of everything else.
    \item Learner pulls an arm $J_t \in [K]$.
    \item Learner obtains the reward $X_{J_t,t}$, and
observes some information about $X_t$. (We'll vary the amount of information in the parts below.)
\end{enumerate}

The regret of a given algorithm is given by
\begin{equation*}
\regret(T) := \max_{j \in [K]} \E\left[ \sum_{t=1}^{T} 
 X_{j,t}\right] -  \E\left[\sum_{t=1}^{T} X_{J_t, t} \right]
.\end{equation*}


We'll first consider the case where Learner gets to see the entirety of $X_t$ after pulling arm $J_t$ (full information).

\begin{qlist}
\item \pts{30}
    Design a learning algorithm that achieves a $\bigO \left(\frac{\log K}{\Delta_{\min}} \right)$ problem-dependent regret bound, and $\bigO \left(\sqrt{T \log (K)} \right)$ worst-case regret bound.
    \textcolor{black}{%
    Here $\Delta_{\min} = \min_{j \in [K]: \Delta_j >0} \Delta_j$ is the minimum mean reward gap. Note that the problem-dependent regret bound should not depend on $T$.
    }

    \meta{You also need to prove that your algorithm achieves these bounds. :)}

    \hint{Algorithm design: Since Learner can observe the reward vector $X_t$ at the end of each round, exploration is not needed.}

    \hint{Problem-dependent regret analysis: It's easier to first assume all the sub-optimal arms have the same gap $\Delta$, do that analysis, then use the doubling trick to estimate $\Delta_j$ and drop that assumption.}
    
    \hint{Worst-case regret analysis: you can set $\Delta_0 = \sqrt{\frac{\log K}{T}}$ to partition the arm set into two groups.}

    \begin{answer}\TODO\end{answer}
\end{qlist}

Now, let's consider a case with less than full information.
Let's assume that $K$ is an even number,
and partition the arms into two disjoint groups:
$C_1 = \left\{ 1,2,\dotsc, K/2 \right\}$ and 
$C_2 = \left\{K/2 +1, \dotsc, K \right\}$.

In this version of the game,
after pulling arm $J_t$,
Learner gets to observe the values of $X_{j,t}$ for all $j$ in the same group as $J_t$, including $J_t$ itself.
No information is provided about the rewards of arms in the other group.

\begin{qlist}[resume]
\item \pts{25} Design a learning algorithm that achieves a $\displaystyle \sum_{g = 1}^{2} \bigO \left(\frac{\log (T)}{\Delta^2_{g,\min}} \cdot \Delta_{g, \max}\right)$ problem-dependent regret bound, where $\Delta_{g,\min} = \min_{j \in C_g: \Delta_j>0} \Delta_j$ is the minimum mean reward gap among all the sub-optimal arms in group $C_g$, and $\Delta_{g, \max} = \max_{j \in C_g} \Delta_j$ is the maximum mean reward gap among all the sub-optimal arms in group $C_g$.

\hint{Now, we do need to do some exploration, as Learner can only observe a group of arms in each round. However, within each group, pure exploitation is enough. }

\begin{answer}\TODO\end{answer}


\item \pts{5 challenge} Design a learning algorithm that achieves a $\displaystyle \sum_{g = 1}^{2} \bigO \left(\frac{\log (T)}{\Delta_{g,\min}} \right)$ problem-dependent regret bound.

 \hint{Use the doubling trick.}

 \begin{answer}\TODO\end{answer}
\end{qlist}

\clearpage
\section{Piecewise-constant functions \pts{35 points + 5 challenge}}

Let $a = (a_1, a_2, \dots, a_k, 0, 0, \dots)$
be an eventually-zero sequence
with entries $a_i \in \{0, 1\}$.
Then define a hypothesis $h_a : \R_{> 0} \to \{0, 1\}$ by
\[
    h_a(x) = a_{\ceil{x}} = \begin{cases}
    a_1 & \text{if } 0 < x \le 1 \\
    a_2 & \text{if } 1 < x \le 2 \\
    &\vdots
\end{cases}
.\]
Consider the hypothesis class of all such functions:
$\cH = \{ h_a : \forall i \in \NN, a_i \in \{0, 1\} \text{ and } a \text{ is eventually zero} \}$.
We'll use the 0-1 loss in this question.

\begin{qlist}
\item \label{q:const:vc} \pts{5} Show $\VCdim(\cH) = \infty$.
\begin{answer}\TODO\end{answer}

\item \label{q:const:noshatter} \pts{10}
    Give an example of a continuous distribution $\xdist$ on (a subset of) $\R_{> 0}$ where,
    for some $m < \VCdim(\cH)$, samples $S_x \sim \xdist^m$ have probability zero of being shattered by $\cH$.
    Thus prove that, for any $\dist$ with this $x$ marginal $\xdist$,
    ERM over $\cH$
    obtains error at most $\inf_{h \in \cH} L_\dist(h) + \eps(m, \delta)$ 
    with probability at least $1 - \delta$,
    where $\eps(m, \delta)$ is some finite quantity such that $\lim_{m \to \infty} \eps(m, \delta) = 0$ for each $\delta$.
    \textcolor{black}{By comparison, the VC bound would only show the approximation error is at most $\infty$.}
\begin{answer}\TODO\end{answer}

\item \label{q:const:srm} \pts{10}
    Write $\cH = \cH_1 \cup \cH_2 \cup \cdots$, where each $\cH_k$ has a finite VC dimension,
    and write down an explicit SRM algorithm that nonuniformly learns $\cH$.
    
    \meta{By ``an explicit algorithm,'' I mean to expand out things like the uniform convergence bound for $\cH_k$.
    It's okay to write something as an argmin over $\cH$ like in equation (9.3) of the notes, if you say what $k_h$ is for a given $h$ and give the value of the corresponding Rademacher complexity.
    It's also okay to appeal to the SRM algorithm pseudocode from the notes, as long as you say what's in each $\cH_k$, what the $\eps_k$ functions are, and how to compute the stopping condition.}
\begin{answer}\TODO\end{answer}


\item \label{q:const:hardsrm} \pts{3 challenge} \textbf{Challenge question:}
    Suppose that instead of eventually-zero sequences,
    we allowed all possible sequences $a \in \{0, 1\}^{\mathbb N}$,
    e.g.\ the $a$ that infinitely alternates between 0 and 1 is now an option.
    Prove that this bigger $\cH'$ is \emph{not} nonuniformly learnable.
    \meta{This implies a sort of no-free-lunch theorem for nonuniform learnability.}

    \hint{Try a \href{https://en.wikipedia.org/wiki/Cantor's_diagonal_argument}{diagonalization argument}.}
\begin{answer}\TODO\end{answer}
\end{qlist}

The following result will be useful momentarily:
\begin{prop} \label{q:const:qs-thm}
    Let $\dist$ be any distribution over the positive integers $\NN$,
    and $S \sim \dist^m$.
    Define a random variable
    $Q_S$ to be the number of unique samples seen out of $m$ draws,
    $Q_S = \abs{ \bigl\{ n : n \in S \bigr\} }$.
    Then $\E Q_S = o(m)$.
\end{prop}
(Recall \href{https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation}{little-o notation} 
in this case is equivalent to saying $\lim_{m \to \infty} \frac{\E Q_S}{m} = 0$.)


\begin{qlist}[resume]

\item \label{q:const:radsmall} \pts{5}
    Prove that, for \emph{any} $\xdist$,
    $\E_{S_x \sim \xdist^m} \Rad(\cH\rvert_{S_x}) \to 0$
    as $m \to \infty$.

    \hint{You can use \cref{q:const:qs-thm}, if you reframe the problem slightly.}
\begin{answer}\TODO\end{answer}

\item \label{q:const:qs} \pts{2 challenge}
    \textbf{Challenge question:}
    Prove \cref{q:const:qs-thm}.
\begin{answer}\TODO\end{answer}


\item \label{q:const:oops} \pts{5}
    An absentminded professor once made the following argument on the \emph{final exam} for a course:
    \begin{displayquote} \itshape
        If a hypothesis class has $\E_{S_x \sim \xdist^m} \Rad(\cH\rvert_{S_x}) \to 0$ for all $\xdist$,
        then for all realizable $\dist$,
        \[ L_\dist(\hat h_S) \le \E_{S_X \sim \xdist^m} \Rad(\cH\rvert_{S_x}) + \sqrt{\frac{1}{2m} \log\frac1\delta} \to 0 .\]
        Thus, by the ``fundamental theorem of statistical learning,'' $\cH$ must have finite VC dimension.
    \end{displayquote}
    Clearly this argument is wrong, since it puts \cref{q:const:vc,q:const:radsmall} in contradiction.
    What was her mistake?
\begin{answer}\TODO\end{answer}
\end{qlist}
\end{document}
