\documentclass[a4paper, 11pt, landscape]{extarticle}
\usepackage{multicol}
\usepackage[margin=0.5cm]{geometry}
\usepackage{enumitem}
\setlist{leftmargin=3mm, nosep}
% or \setlist{noitemsep} to leave space around whole list

\usepackage{nicefrac}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage[dvipsnames]{xcolor}
\let\tc\textcolor
\definecolor{g}{RGB}{50, 168, 82}
\definecolor{r}{RGB}{194, 40, 10}
\definecolor{b}{RGB}{27, 143, 181}
\definecolor{p}{RGB}{120, 17, 184}
\definecolor{o}{RGB}{222, 154, 60}

\setlength{\columnseprule}{1pt}

\begin{document}

% 3-column layout
\begin{multicols*}{3}

\begin{enumerate}[label={}]
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{General definitions}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item $ \mathcal{N}(y;\Sigma,\mu) = 
        \frac{1}{\sqrt{(2\pi)^n |\Sigma|}}
        \exp\bigg(-\frac{1}{2}(y-\mu)^T \Sigma^{-1} (y-\mu)\bigg) $
    \item need only $n^2$ params for joint instead of $2^n-1$
    
    \item \underline{entropy} $ H(q) = 
        -\int q(\theta) \log q(\theta) d\theta =
        \mathbb{E}_{\theta \sim q}\big[-\log q(\theta)\big] $
        
    \item \underline{mutual info} $ I(X;Y) = H(X) - H(X|Y) $ (symmetric)
    
    \item \underline{KL div.} $ KL(q||p) = 
        \int q(\theta)\log\frac{q(\theta)}{p(\theta)}d\theta = 
        \mathbb{E}_{\theta\sim q}\big[\log\frac{q(\theta)}{p(\theta)}\big]$
    \item non-negative, zero iff q and p agree a.e., not symmetr.
    
    \item \underline{Jensen's inequality}: $ g(\mathbb{E}[X]) \leq \mathbb{E}[g(X)] $ for g convex, else flipped (e.g. $ \log(\mathbb{E}[X]) \geq \mathbb{E}[\log(X)] $
    
    \item \underline{Hoeffding's inequality}: for $f$ bounded in $[0,C]$
    \item $ p\big(|\mathbb{E}_p[f(X)] - 
        \frac{1}{N}\sum_if(x_i)| > \epsilon\big) \leq 
        2\exp(-2N\epsilon^2/C^2)$
        
    \item \underline{Robins-Monro conditions}: $ \sum_t \epsilon_t = \infty, \sum_t \epsilon_t^2 < \infty $
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Bayesian linear regression (BLR)}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item BLR makes same assumptions as ridge regression: cond. idd Gaussian noise, Gaussian prior
    
    \item \underline{RR} = MAP estimation for LR ($y = w^Tx)$, i.e. returns single model, \tc{r}{no uncertainty qualification} (collapses all uncertainty onto mode of posterior $p(w|X,y)$)
    
    \item \underline{BLR} reasons about full $p(w|X,y) \sim
        \mathcal{N}(y;\mu,\Sigma) $
    \item $ \mu = (X^TX + \sigma_n^2 I)^{-1} X^Ty $ ; 
        \tc{g}{$ \Sigma = (\sigma_n^{-2}X^TX + I)^{-1} $}
    \item prediction: $ p(y^*|X,y,x^*) \sim
        \mathcal{N}(\mu^Tx^*,\tc{o}{x^{*T}\Sigma x^*} + \tc{p}{\sigma_n^2}) $
    \item $\Rightarrow$ separation of \tc{o}{epistemic uncertainty} (about $f^*$/model due to lack of data) and \tc{p}{aleatoric uncertainty} (irreducible noise from $y^* = f^* + \epsilon$) 
    
    \item independent noise $\Rightarrow$ \underline{recursive Bayesian updates}, i.e. use posterior from last iteration as prior:
    \item $ p(w|y_{1:j+1}) = 
        \frac{1}{Z} p(w|y_{1:j}) p(y_{j+1}|w,y_{1:j}) $
    \item $ w^{(j+1)} = f(w^{(j)},y_{j+1},x_{j+1}) $
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Kalman/Bayesian filtering}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item motion model: $ x_{t+1} = Fx_t + \epsilon_t $ ; 
        $ \epsilon_t \sim \mathcal{N}(0, \Sigma_x) $
    \item sensor model: $ y_t = Hx_t + \eta_t $ ;
        $ \eta_t \sim \mathcal{N}(0, \Sigma_y) $
    \item $F, H$ known and deterministic, KF resembles HMM
    
    \item \underline{Kalman update}: \hfill $ \mu_{t+1} = 
        F\mu_t + K_{t+1}(y_{t+1} - HF\mu_t) $
    \item \hfill $ \Sigma_{t+1} = 
        (I - K_{t+1})(F\Sigma_tF^T + \Sigma_x) $
        
    \item \underline{Kalman gain}: $ K_{t+1} = 
        (F\Sigma_tF^T + \Sigma_x)H^T(H(F\Sigma_tF^T + \Sigma_x)H^T + \Sigma_y)^{-1} $, compute $\Sigma_t, K_t$ offline (indep. of obs.)
    \item BLR = KF with $w$ as hidden vars., $F = I, \sigma_x^2$ = 0
    \item KF special case of GP with cond. indep. structure
    
\end{enumerate}

\columnbreak
\begin{enumerate}[label={}]
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Gaussian processes}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item instead of random $w$, think of random responses 
    \item $ f = Xw \sim \mathcal{N}(0, \sigma_p^2XX^T) $ 
        s.t. $XX^T = K$, $ K_{ij} = x_i^Tx_j $
    \item Gaussians over functions instead of RVs/points
    \item prior $p(f)$ encodes smoothness ass. on functions
    \item posterior $p(f|data)$ encodes agreement with data
    \item \tc{g}{uncertainty, tractable inference for finite marginals}
    \item mean func. $\mu$, covariance func. $k$ (BLR for lin. kernel)
    
    \item \underline{prediction}: closed form, posterior cov. $k'$ indep. of $y_A$
    \item $ \mu'(x) = 
        \mu(x) + k_{x,A}(K_{AA}+\sigma^2I)^{-1}(y_A - \mu_A) $
    \item $ k'(x,x') =
        k(x,x') - k_{x,A}(K_{AA}+\sigma^2I)^{-1}k_{x,A}^T $
    \item sampling from GP: $ f = [f_1, ..., f_n] \sim 
        \mathcal{N}(0, K_x) $
    \item product rule $\Rightarrow$ forward sampling (\tc{r}{fully sequential}):
    \item sampling from univariate Gaussians $ f_n \sim 
        p(f_n|f_{1:n-1}) $
        
    \item \underline{opt. kernel params}: 1) CV on predictive performance 
    \item 2) Bayesian, i.e. max. marg. likelihood: 
    \item $ \hat\theta = 
        \arg\max_\theta \int p(y|f,X)p(f|\theta)df $ (general)
    \item $ \hat\theta = 
        \arg\min_\theta \tc{b}{\frac{1}{2}\log|K_y(\theta)| + 
        \frac{1}{2}y^TK_y(\theta)y} $ (Gaussians)
    \item solve using GD, i.e. $ \theta^{(t+1)} = 
        \theta^{(t)} - y_t\nabla \tc{b}{L(\theta)} $
    \item \tc{g}{reduces overfitting}, but depends heavily on prior
    
    \item \underline{comp. cost}: LSE in $|A|$ unknowns $\Rightarrow$     \tc{r}{$\mathcal{O}(|A|^3)$}
    \item acceleration methods: 1) parallelization (still $\mathcal{O}(|A|^3)$)
    \item 2) local GP methods: only consider $x'$ if $|k(x,x')| > \tau$
    \item 3) kernel approx.: Fourier for stationary kernels
    \item 4) inducing point: ignore points (e.g. in clusters)
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Approximate inference}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \underline{Variational inference}:
    \item for BLR and GPR everything closed form, generally not the case $\Rightarrow$ need approximations
    \item can evaluate joint $p(y,\theta)$ but not normalizer $Z$
    \item replace high-dim. integrals by optimization
    \item $ p(\theta|y) =
        \frac{1}{Z}p(y,\theta)\approx q(\theta|\lambda) $
    \item $ q^* = 
        \arg\min_q KL(q||p) = \arg\min_\lambda KL(q_\lambda||p) $
    \item prefer $\arg\min_q KL(p||q)$(p in q), but harder to opt.
    \item $ q^* = 
        \arg\max_q \tc{b}{\mathbb{E}_{\theta\sim q}[\log p(y|\theta)] - 
        KL(q||p(\cdot))}$
    \item regularizer: want $q$ close to prior $p(\cdot)$
    \item Jensen's inequality $\Rightarrow$ ELBO $\tc{b}{L(q)} \leq \log p(y) $
    \item to use SGD to max. $L(\lambda)$, need reparameterization: 
    \item $ q(\theta|\lambda) = 
        \phi(\epsilon)|\nabla_\epsilon g(\epsilon;\lambda)|^{-1} $ ;
        $ \epsilon \sim \phi, \theta = g(\epsilon, \lambda) $
    \item $ \nabla_\lambda\mathbb{E}_{\theta\sim q_\lambda}[f(\theta)] =     \nabla_\lambda\mathbb{E}_{\epsilon\sim\phi}
        [f(g(\epsilon;\lambda))] = 
        \mathbb{E}_{\epsilon\sim\phi}
        [\nabla_\lambda f(g)] $
        
\end{enumerate}
\columnbreak
\begin{enumerate}[label={}]
    \item \underline{Laplace approximation}:
    \item 2nd-order Taylor expansion around $\hat\theta$ to construct Gaussian: $ q(\theta) \sim
        \mathcal{N}(\theta;\hat\theta,\Lambda^{-1}) $ ; 
        $ \Lambda = -\nabla\nabla\log p(\hat\theta|y) $
    \item $Z$ const. in optimization for $\hat\theta$ and calculation for $\Lambda$
    \item \tc{r}{overconfident}, does not consider cov. when seeking $\hat\theta$
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Markov Chain Monte Carlo (MCMC)}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item vs. VI: \tc{g}{returns accurate result}, \tc{r}{higher comp. cost}
    \item seek to approx. p using samples constructed by a markov chain (\underline{law of large numbers}, need $\theta^{(i)}$ indep.)
    \item $ p(y^*|X,y,x^*) = 
        \mathbb{E}_{\theta\sim p(\cdot|X,y)}[p(y^*|x^*,\theta)] \approx
        \frac{1}{N} \sum_i f(\theta^{(i)})$
    \item need $ N \geq \frac{C^2}{2\epsilon^2}\log\frac{2}{\delta} $ for error $\leq \epsilon$ with prob. $ \geq 1-\delta $
    \item create MC with $ \pi = P(x) = 
        \frac{1}{Z}P(y)P(x|y) = \frac{1}{Z}Q(x) $
    \item guaranteed by \underline{detailed balance}:
    \item $ \frac{1}{Z}Q(x)P(x'|x) = \frac{1}{Z}Q(x')P(x|x') $
    
    \item \underline{Metropolis-Hastings}: (\tc{p}{perf. highly dependent on R!})
    \item 1) given $X_t = x$, sample proposal $ x'\sim R(X'|X=x) $
    \item 2) set $X_{t+1} = x'$ with prob. $\alpha$, else $X_{t+1} = x$
    \item $ \alpha = \min\big\{1, 
        \frac{Q(x')R(x|x')}{Q(x)R(x'|x)}\big\} $
        
    \item \underline{Gibbs}:
    \item 1) init. assignment $x^{(0)}$ to all variables
    \item 2) fix observed vars. $X_B$ to their observed values $x_B$
    \item 3) either random order (\tc{g}{detailed balance}): pick $i$ unif. at random, update $x_i\sim P(X_i|v_i)$ or practical variant (no det. bal. but has correct $\pi$): set $x^{(t)} = x^{(t-1)}$, then update all $x_i$ except those in $B$
    \item $Z = \sum_x Q(X_i=x,v_i)$ is easy to calculate $\Rightarrow$ \tc{g}{sampling from $X_i$ given assignment to all other vars. is efficient}
    \item \tc{r}{$x^{(t)}$ dep. on $x^{(t-1)}$ $\Rightarrow$ loln, Hoeffding's no longer hold}
    \item only ergodic MC $ \lim_{N\rightarrow\infty} 
        \frac{1}{N}\sum_i f(x_i) = \mathbb{E}_{x\sim \pi}[f(x)]$ 
        
    \item \underline{MCMC for continuous RVs}:
    \item proposal distr. either random (simple, uninformed) or in gradient direction (\underline{MALA}):
    \item $ R(x'|x)\sim\mathcal{N}(x';x - \tau\nabla f(x), 2\tau I) $
    \item $ \alpha = \min\big\{1, e^{f(x) - f(x')}\big\} $ for $ p = 
        \frac{1}{Z}e^{-f(x)}$
    \item \tc{g}{converges to $\pi$ for f convex $\Leftrightarrow$ p log-concave}
    \item \tc{r}{requires access to full energy func. f}
    \item $\Rightarrow$ \underline{SGLD}:
    \item replace full gradient by unbiased estimate (mini-batch), always accept but reduce step size $\eta_t$ over time
    \item $\Rightarrow$ SGD + Gaussian noise, \tc{g}{converges for $\eta_t \in \mathcal{O}(t^{-1/3})$}
    
\end{enumerate}
\columnbreak
\begin{enumerate}[label={}]
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Bayesian deep learning}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item heteroscedastic noise: noise depends on input
    \item $\Rightarrow$ model mean and (log) var as outputs of NN
    \item $ p(y|x,\theta) =
        \mathcal{N}(y;f_1(x,\theta),e^{f_2(x,\theta)}) $
    \item MAP est.: $ \hat\theta = 
        \arg\min_\theta - \log p(\theta) - \sum_i \log p(y_i|x_i,\theta)$
    \item \underline{prediction} $ \tc{b}{p(y^*|X,y,x^*)} = 
        \int p(y^*|x^*,\theta)p(\theta|X,y)d\theta$
    \item integrals intractable $\Rightarrow$ approximate inference:
    
    \item \underline{Bayes by backprop}: 
    \item \tc{b}{llh} $ \stackrel{\text{VI}}{\approx}
        \mathbb{E}_{\theta\sim q(\cdot|\lambda}[p(y^*|x^*,\theta)]
        \stackrel{\text{MC}}{\approx}
        \frac{1}{m}\sum_j p(y^*|x^*,\theta^{(j)}) $ 
    \item $\Rightarrow$ mixture of Gaussians
    \item $ \mathbb{E}[\tc{b}{llh}] \approx \bar\mu(x^*) = 
        \frac{1}{m}\sum_j\mu(x^*,\theta^{(j)})$
    \item $ \mathrm{Var}(\tc{b}{llh}) = 
        \tc{o}{\mathrm{Var}(\mathbb{E}_y[y^*|x^*,\theta])} +
        \tc{p}{\mathbb{E}_\theta[\mathrm{Var}(y^*|x^*,\theta)]} $
    \item $ \approx
        \tc{o}{\frac{1}{m}\sum_j(\mu(x^*,\theta^{(j)})-\bar\mu(x^*))^2} +\tc{p}{\frac{1}{m}\sum_j\sigma(x^*,\theta^{(j)})}$
    
    \item \underline{MCMC for BNNs}:
    \item apply SGLD, MALA (only need stoch. grads of joint)
    \item $\Rightarrow$ produce sequence $\theta^{(1)}, ..., \theta^{(T)}$, impossible to store all samples/models, hard to determine burn-in
    \item 1) subsampling: keep only a subset of $m<T$ models
    \item 2) Gaussian approx.: running averages for $\mu_i,\sigma_i^2$
    
    \item \underline{specialised inference techniques for BNNs}:
    \item dropout regularization: randomly ignore hidden units during each SGD iteration (forward and backprop.)
    \item view as VI: $ q(\theta|\lambda) = 
        \prod_jp\delta_0(\theta_j) + (1-p)\delta_{\lambda_j}(\theta_j)$
    \item probabilistic ensembles of NNs: variation of $\theta^{(j)}$ shows uncertainty $\Rightarrow$ bootstrap, get MAP on $D_j$ to get $\theta^{(j)}$
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Active learning}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item use \tc{o}{epistemic} and \tc{p}{aleatoric} uncertainty to decide which data to collect (e.g. where to place sensors)
    \item want points $S$ which max. info gain (\tc{r}{NP-hard})
    \item \underline{greedy algo./uncertainty sampling}: choose $x_{t+1} = \arg\max_x \sigma_t^2(x)$ (\tc{r}{only considers epistemic uncertainty})
    \item for \underline{heteroscedastic case}, need $x_{t+1} = 
        \arg\max_x \frac{\tc{o}{\sigma_f^2(x)}}{\tc{p}{\sigma_n^2(x)}}$ as \tc{p}{aleatoric uncertainty} no longer const. in $x$
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Bayesian optimization} (exploration-exploitation)
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item use that similar alternatives have similar performance
    \item \underline{multi-armed bandits}: pick $x_t$, observe $y_t = f(x_t) + \epsilon_t$
    \item cum. regr. $ R_T = \sum_t \max_x f(x) - f(x_t) $ ; 
    want $\frac{R_T}{T} \rightarrow 0$
    
\end{enumerate}
\columnbreak
\begin{enumerate}[label={}]
    \item \underline{acquisition functions}: 
    \item GP-UCB: focus exploration on regions where upper conf. bound $\geq$ best lower conf. bound
    \item $ x_t = \arg\max_x \mu_{t-1}(x) + \beta_t\sigma_{t-1}(x) $
    (\tc{r}{gen. non-convex})
    \item \tc{r}{how to choose $\beta_t$?}, \tc{g}{naturally trades off e-e}
    \item Thompson: $ x_t = \arg\max_x \tilde{f}(x) $ ; 
        $ \tilde{f}\sim p(f|x_{1:t},y_{1:t}) $
    \item \tc{g}{randomness in $\tilde{f}$ enough to trade off e-e}
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Markov decision processes (MDPs)}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item states, actions, transition probas. and reward function
    \item $ V^\pi(x) =
        r(x,\pi(x)) + \gamma\sum_{x'}P(x'|x,\pi(x))V^\pi(x')$
    \item can compute $V^\pi = r^\pi + \gamma T^\pi V^\pi$ exactly by solving LSE
    \item approx. by fixed point iteration: $V_t^\pi = 
        r^\pi + \gamma T^\pi V_{t-1}^\pi$
    \item \tc{g}{converges exponentially}
    
    \item every $V$ induces a (greedy) $\pi$ and vice versa:
    \item $V \leadsto \pi_g(x) = 
        \arg\max_a r(x,a) + \gamma\sum_{x'}P(x'|x,a)V(x')$
    \item \underline{Bellman thm}: $\pi$ optimal $\Leftrightarrow$ greedy w.r.t. induced $V$
    
    \item \underline{policy iteration}: init $\pi$, until convergence:
    \item 1) comp. $V^\pi(x)$ 2) comp. $\pi_g$ w.r.t. $V^\pi$ 3) $\pi = \pi_g$
    \item \tc{g}{$V^\pi$ monotonically increases, converges to optimal $\pi$}
    \item complexity: need to solve LSE for $V$
    
    \item \underline{value iteration}: Bellman+FPI $V_0(x) = \max_a r(x,a)$
    \item $ Q_t(x,a) = 
        \max_a r(x,a) + \gamma\sum_{x'}P(x'|x,a)V_t(x') $
    \item $V_t(x) = \max_a Q_t(x,a)$, break if $\|V_t-V_{t-1}\|_\infty \leq \epsilon$
    \item $\leadsto \pi_g$, \tc{g}{converges to $\epsilon$-optimal $\pi$ in $\mathcal{O}(ln\nicefrac{1}{\epsilon})$ iterations}
    
    \item \underline{POMDP}: (control. HMM); $P(X_{t+1}|X_t,A_t)$, \tc{p}{$P(Y_t|X_t)$}
    \item \tc{g}{very powerful} \tc{r}{but generally extremely intractable}
    \item $\Rightarrow$ belief-state MDPs (use Bayesian filtering):
    \item beliefs $ P(X_t|y_{1:t}) $ given noisy observations $y$
    \item $ b_{t+1}(x) = P(X_{t+1}=x|y_{1:t+1}) = 
        \frac{1}{Z} P(y_{t+1}|x)P(X_{t+1}=x|y_{1:t})$ ; $r(b_t,a_t) = \sum_x b_t(x)r(x,a_t)$
    \item most belief states never reached
    \item dyn. progr., point based methods, policy grads
    
    \hfill
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \textbf{Reinforcement learning}
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \underline{credit assignment problem}: which $a_i$ got me to this $r$?
    \item data not iid, depends on our actions $\Rightarrow$ e-e dilemma
    
    \item \underline{model-based RL}: learn MDP from data
    \item estimate $P(x'|x,a), r(x,a)$ e.g. by MLE (counts)
    \item \tc{r}{store r,P; solve est. MDP up to $|X|\cdot|A|$ times}
    \item $\epsilon$-greedy: random $a_t$ with prob. $\epsilon_t$, else best $a_t$
    \item \tc{g}{conv. to optimal $\pi$}, \tc{r}{considers suboptimal actions}
    
\end{enumerate}
\columnbreak
\begin{enumerate}[label={}]
    \item \underline{$R_{max}$}: "optimism in the face of uncertainty"
    \item init $r(x,a) = R_{max}, P(x^*|x,a) = 1$, $\pi$ opt. w.r.t. $r, P$
    \item repeat: exec. $\pi$, obs. $(x,a)$, update $r$, est. $P(x'|x,a)$, recompute $\pi$ w.r.t. $r,P$ after $n\in \mathcal{O}(\frac{R_{max}^2}{\epsilon^2}\log\frac{1}{\delta})$ obs. 
    
    \item \underline{model-free RL}: est. $V^\pi$ directly given $\pi$
    \item \underline{TD-learning}: (on-policy), init $V_0^\pi$, $\pi \leadsto (x,a,r,x')$
    \item $ V_{t+1}^\pi(x) = 
        (1 - \alpha_t)V_t^\pi(x) + \alpha_t(r + \gamma V_t^\pi(x'))$
    \item i.e. use bootstrapping, one-sample est. of long-term $r$
    
    \item \underline{Q-learning}: (off-policy) $a\leadsto (x,a,r,x')$
    \item $ Q_{t+1}(x,a) = 
        (1 - \alpha_t)Q_t(x,a) + 
        \alpha_t(r + \gamma\max_{a'}Q_t(x',a'))$
    \item choose $ Q_0(x,a) = 
        \frac{R_{max}}{1-\gamma} \prod_t (1-\alpha_t)^{-1}$ for e-e tradeoff
    
    \item \underline{large state spaces}: learn approx. $V(x;\theta), Q(x,a;\theta)$
    \item neural-fitted Q-iteration (\underline{DQN}): collect dataset D
    \item $ L(\theta) = 
        \sum_{\cdot\in D} (r + \gamma\max_{a'}Q(x',a';\theta^{old}) -
        Q(x,a;\theta))^2$
    \item \tc{r}{max. bias, too optimistic about noisy est. of Q}
    \item \underline{DDQN}: decouple max.: $a^*(\theta) = 
        \arg\max_{a'} Q(x',a';\theta)$
    \item $ L(\theta) = 
        \sum_{\cdot\in D} (r + 
        \gamma Q(x',a^*(\theta);\theta^{old}) -Q(x,a;\theta))^2$
    
    \item \underline{large action spaces}: policy search, learn $\pi(x;\theta)$
    \item 1) policy gradients: $ J(\theta) = 
        \frac{1}{m}\sum_j r(\tau^{(j)}) $ (on-policy)
    \item $ \nabla J(\theta) = 
        \nabla \mathbb{E}_{\tau\sim\pi_\theta}[r(\tau)] = 
        \nabla \mathbb{E}_{\tau\sim\pi_\theta}[
        r(\tau)\nabla\log \pi_\theta(\tau)]$
    \item MDP structure $\Rightarrow 
        \nabla \mathbb{E}_{\tau\sim\pi_\theta}[
        r(\tau)\sum_t\nabla\log \pi(a_t|x_t;\theta)]$
    \item \tc{g}{unbiased} \tc{r}{but very large variance} $\Rightarrow$ baselines:
    \item $\nabla J(\theta) =
        \nabla \mathbb{E}_{\tau\sim\pi_\theta}\big[
        \sum_i\gamma^t(G_t - b_t)\nabla\log \pi(a_t|x_t;\theta)\big]$
    \item e.g. $G_t = \sum_{t'=t}\gamma^{t'-t}r_{t'}$ rews-to-go, $b_t = 
        \frac{1}{T}\sum_t G_t$
    \item 2) \underline{actor-critic}: (\tc{g}{non-episodic})
    \item $ \nabla J(\theta_\pi) = 
        \mathbb{E}_{(x,a)\sim\pi_\theta}[
        Q(x,a;\theta_Q)\nabla\log\pi(a|x;\theta_\pi)]$
    \item $ \theta_\pi \leftarrow 
        \theta_\pi + \eta_t Q(x,a;\theta_Q)\nabla\log\pi(a|x;\theta_\pi) $ ; 
        $ \theta_Q \leftarrow 
        \theta_Q - \eta_t(Q(x,a;\theta_Q) - r - 
        \gamma Q(x',\pi(x';\theta_\pi);\theta_Q))\nabla Q(x,a;\theta_Q) $
    \item \underline{off-policy AC}: (DDPG, resp. TD3 to avoid max. bias)
    \item $ L(\theta_Q) = 
        \sum_{\cdot\in D}(r + 
        \gamma Q(x',\pi(x';\theta_\pi);\theta_Q^{old}) - 
        Q(x,a;\theta_Q))^2$
    \item $ \nabla J(\theta_\pi) = 
        \mathbb{E}_{x\sim\mu}[\nabla Q(x,\pi(x;\theta);\theta_Q)]$ (i.e. w.r.t. $\pi_G$)
    \item \tc{r}{only for determin. $\pi$}, \tc{g}{add action noise for exploration}
    \item random. $\pi$: A use reparam. to pull $\nabla_{\theta_\pi}$ into 
        $\mathbb{E}_{a\sim\pi(x,\theta_\pi)}$
    \item soft AC: $ J_\lambda(\theta) = 
        J(\theta) + \lambda H(\pi_\theta)$ (entropy regulariz.)
        
    \item \underline{model-based deep RL}: \tc{g}{smaller sample complexity}
    \item MPC: $ \max_{a_{0:\infty}}
        \sum_t\gamma^t r(x_t,a_t) $ s.t. $x_{t+1} = f(x_t,a_t)$
    \item finite horizon, unroll: $ \max_{a_{t:t+H-1}}
        \sum_\tau\gamma^\tau r(x_\tau(a_{t:\tau-1}),a_\tau) $
    \item \tc{g}{analytic grads} \tc{r}{local min., exploding/vanishing grads}
    \item use heuristics, e.g. random shooting
    \item sparse r, add (off-policy) V estimate $ + \gamma^H V(x_{t+H})$
    \item unknown (f, r): regression (Bayesian learning, e-e)
    
    
    
\end{enumerate}

\end{multicols*}
\end{document}
