Algorithm.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1.25in]{geometry}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm2e}

% Common mathbb commands
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
% Common "curly" (mathcal) commands
\newcommand{\aA}{\mathcal{A}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\hH}{\mathcal{H}}
\newcommand{\xX}{\mathcal{X}}
\newcommand{\gG}{\mathcal{G}}
\newcommand{\fF}{\mathcal{F}}
\newcommand{\zZ}{\mathcal{Z}}
\newcommand{\rR}{\mathcal{R}}
\newcommand{\mM}{\mathcal{M}}

\newcommand{\twiddle}{\sim}
\newcommand{\err}{\ensuremath{\mbox{err}}}
\newcommand{\sign}{\ensuremath{\mbox{sign}}}
\newcommand{\co}{\ensuremath{\mbox{co}}}

\renewcommand{\part}[1]{\hfill\\\textbf{(#1)}\ }

\newcommand{\beats}{\ensuremath{\gtrdot}}

%Handy macro template
%\newcommand{\whatever}{\ensuremath{...}\xspace}

\title{Machine Learning Project}
\author{Devon Loehr (dloehr)}
\date{\today}

\begin{document}
\maketitle

We define an \emph{RPS-like game} to be a set $\mM$ of moves equipped with an irreflexive, antisymmetric binary relation \beats. The game is played by two players who each secretly select a move from $\mM$. A player wins a round if the move they selected beats the move the other player selected. If neither move beats the other, the players tie.

\begin{algorithm}[H]
	\SetAlgoLined
	\KwIn{RPS-like game $(\mM, \beats)$, $N$ predictions $\xi_i \in \mM$, $\beta \in (0, 1)$}
	Give each expert a weight $w_i = 1$\;
	\While{ True }{
		\For {$m \in \mM$}{ 
			let $P_m = \sum_{i=1}^N w_i \cdot 1\{\xi_i = m\}$\; }
		\For {$m \in \mM$}{ 
			let $V_m = \sum_{m' \beats m} P_{m'} - \sum_{m \beats m'} P_{m'}$\; }
		Play $\arg \max_m V_m$\;
		Observe opponent's move $\hat m$\;
		\For {$i = 1, \dots, N$}{ 
			$w_i = w_i \cdot \beta ^ {1\{\xi_i \neq \hat m\}}$\; }
	}
	\caption{Deterministic}
\end{algorithm}


\begin{algorithm}[H]
	\SetAlgoLined
	\KwIn{RPS-like game $(\mM, \beats)$, $N$ predictions $\xi_i \in \mM$, $\beta \in (0, 1)$}
	Give each expert a weight $w_i = 1$\;
	\While{ True }{
		\For {$m \in \mM$}{
			let $P_m = \sum_{i=1}^N w_i \cdot 1\{\xi_i = m\}$\; }
		\For {$m \in \mM$}{ 
			let $V_m = \sum_{m' \beats m} P_{m'} - \sum_{m \beats m'} P_{m'}$\; }
		let $Z = \sum_{m'}$\;
		let $D$ be a probability distribution over $\mM$, such that $D(m) = \frac{V_m}{Z}$\;
		play $m \twiddle D$\;
		Observe opponent's move $\hat m$\;
		\For {$i = 1, \dots, N$}{ 
			$w_i = w_i \cdot \beta ^ {1\{\xi_i \neq \hat m\}}$\; }
	}
	\caption{Nondeterministic}
\end{algorithm}

% To Discuss:
% infinite tie chains
% experts converging too quickly?

\end{document}