Revision
Formula sheet
All key equations of Chapters 2–9 with their book numbers. Print with Ctrl+P.
General
Incremental rule
$\textit{New}\leftarrow\textit{Old}+\textit{StepSize}\,[\textit{Target}-\textit{Old}]$
2.4
Step-size conditions
$\sum_n\alpha_n=\infty,\quad\sum_n\alpha_n^2\lt\infty$
2.7
Return
$G_t=\sum_{k=0}^\infty\gamma^kR_{t+k+1}=R_{t+1}+\gamma G_{t+1}$
3.8, 3.9
Unified return
$G_t=\sum_{k=t+1}^{T}\gamma^{k-t-1}R_k$
3.11
Chapter 2 — Bandits
Action value
$q_*(a)=\E[R_t\mid A_t=a]$
§2.1
Sample average
$Q_t(a)=\dfrac{\sum_{i\lt t}R_i\mathbb 1_{A_i=a}}{\sum_{i\lt t}\mathbb 1_{A_i=a}}$
2.1
Greedy
$A_t=\argmax_aQ_t(a)$; ε-greedy picks greedy w.p. $1-\varepsilon+\varepsilon/k$
2.2
Incremental mean
$Q_{n+1}=Q_n+\frac1n[R_n-Q_n]$
2.3
Constant α
$Q_{n+1}=Q_n+\alpha[R_n-Q_n]=(1-\alpha)^nQ_1+\sum_{i=1}^n\alpha(1-\alpha)^{n-i}R_i$
2.5, 2.6
Unbiased constant step
$\beta_n=\alpha/\bar o_n,\ \ \bar o_n=\bar o_{n-1}+\alpha(1-\bar o_{n-1}),\ \bar o_0=0$
2.8, 2.9
UCB
$A_t=\argmax_a\Big[Q_t(a)+c\sqrt{\ln t/N_t(a)}\Big]$
2.10
Soft-max
$\pi_t(a)=e^{H_t(a)}/\sum_be^{H_t(b)}$
2.11
Gradient bandit
$H_{t+1}(a)=H_t(a)+\alpha(R_t-\bar R_t)(\mathbb 1_{a=A_t}-\pi_t(a))$
2.12
Chapter 3 — Finite MDPs
Dynamics
$p(s',r\mid s,a)=\Pr\{S_t=s',R_t=r\mid S_{t-1}=s,A_{t-1}=a\}$
3.2
Derived quantities
$p(s'|s,a)=\sum_rp(s',r|s,a)$, $\ r(s,a)=\sum_rr\sum_{s'}p(s',r|s,a)$
3.4, 3.5
Constant reward
$\sum_k\gamma^k=1/(1-\gamma)$
3.10
State value
$v_\pi(s)=\E_\pi[G_t\mid S_t=s]$
3.12
Action value
$q_\pi(s,a)=\E_\pi[G_t\mid S_t=s,A_t=a]$
3.13
v ↔ q
$v_\pi(s)=\sum_a\pi(a|s)q_\pi(s,a)$; $\ q_\pi(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$
Ex 3.12–13
Bellman for $v_\pi$
$v_\pi(s)=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$
3.14
Bellman for $q_\pi$
$q_\pi(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma\sum_{a'}\pi(a'|s')q_\pi(s',a')]$
Ex 3.17
Optimal values
$v_*(s)=\max_\pi v_\pi(s)$, $\ q_*(s,a)=\max_\pi q_\pi(s,a)=\E[R_{t+1}+\gamma v_*(S_{t+1})\mid s,a]$
3.15–3.17
Bellman optimality $v_*$
$v_*(s)=\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_*(s')]$
3.19
Bellman optimality $q_*$
$q_*(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma\max_{a'}q_*(s',a')]$
3.20
Optimal policy
$\pi_*(s)=\argmax_aq_*(s,a)$; $\ v_*(s)=\max_aq_*(s,a)$
Ex 3.25–27
Reward shift (continuing)
$v_c=c/(1-\gamma)$ added to every value
Ex 3.15
Chapter 4 — Dynamic programming
Policy evaluation
$v_{k+1}(s)=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_k(s')]$
4.5
Deviate once
$q_\pi(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$
4.6
Improvement theorem
$q_\pi(s,\pi'(s))\ge v_\pi(s)\ \forall s\ \Rightarrow\ v_{\pi'}(s)\ge v_\pi(s)\ \forall s$
4.7, 4.8
Greedy improvement
$\pi'(s)=\argmax_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$
4.9
Value iteration
$v_{k+1}(s)=\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_k(s')]$
4.10
Q value iteration
$q_{k+1}(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma\max_{a'}q_k(s',a')]$
Ex 4.10
Chapter 5 — Monte Carlo
Greedy from q
$\pi(s)=\argmax_aq(s,a)$
5.1
ε-greedy improvement
$q_\pi(s,\pi'(s))=\frac{\varepsilon}{|\mathcal A|}\sum_aq_\pi(s,a)+(1-\varepsilon)\max_aq_\pi(s,a)\ge v_\pi(s)$
5.2
IS ratio
$\rho_{t:T-1}=\prod_{k=t}^{T-1}\dfrac{\pi(A_k|S_k)}{b(A_k|S_k)}$
5.3
IS expectation
$\E[\rho_{t:T-1}G_t\mid S_t=s]=v_\pi(s)$
5.4
Ordinary IS
$V(s)=\sum_{t\in\mathcal T(s)}\rho_{t:T(t)-1}G_t\,/\,|\mathcal T(s)|$
5.5
Weighted IS
$V(s)=\sum_{t\in\mathcal T(s)}\rho_{t:T(t)-1}G_t\,/\,\sum_{t\in\mathcal T(s)}\rho_{t:T(t)-1}$
5.6
Incremental weighted
$V_{n+1}=V_n+\frac{W_n}{C_n}[G_n-V_n],\ \ C_{n+1}=C_n+W_{n+1}$
5.8
Per-decision IS
$\tilde G_t=\rho_{t:t}R_{t+1}+\gamma\rho_{t:t+1}R_{t+2}+\dots+\gamma^{T-t-1}\rho_{t:T-1}R_T$
5.14–15
Flat partial return
$\bar G_{t:h}=R_{t+1}+\dots+R_h$; $\ G_t=(1-\gamma)\sum_{h=t+1}^{T-1}\gamma^{h-t-1}\bar G_{t:h}+\gamma^{T-t-1}\bar G_{t:T}$
§5.8
Chapter 6 — TD learning
Constant-α MC
$V(S_t)\leftarrow V(S_t)+\alpha[G_t-V(S_t)]$
6.1
TD(0)
$V(S_t)\leftarrow V(S_t)+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$
6.2
TD error
$\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$
6.5
MC error = Σ TD errors
$G_t-V(S_t)=\sum_{k=t}^{T-1}\gamma^{k-t}\delta_k$ (V fixed)
6.6
Sarsa
$Q(S_t,A_t)\leftarrow Q+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$
6.7
Q-learning
$Q(S_t,A_t)\leftarrow Q+\alpha[R_{t+1}+\gamma\max_aQ(S_{t+1},a)-Q(S_t,A_t)]$
6.8
Expected Sarsa
$Q(S_t,A_t)\leftarrow Q+\alpha[R_{t+1}+\gamma\sum_a\pi(a|S_{t+1})Q(S_{t+1},a)-Q(S_t,A_t)]$
6.9
Double Q-learning
$Q_1(S_t,A_t)\leftarrow Q_1+\alpha[R_{t+1}+\gamma Q_2(S_{t+1},\argmax_aQ_1(S_{t+1},a))-Q_1(S_t,A_t)]$
6.10
Off-policy TD(0)
$V(S_t)\leftarrow V(S_t)+\alpha\rho_{t:t}[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$
Ex 6.7
Chapter 7 — n-step bootstrapping
n-step return
$G_{t:t+n}=R_{t+1}+\gamma R_{t+2}+\dots+\gamma^{n-1}R_{t+n}+\gamma^nV_{t+n-1}(S_{t+n})$
7.1
n-step TD
$V_{t+n}(S_t)=V_{t+n-1}(S_t)+\alpha[G_{t:t+n}-V_{t+n-1}(S_t)]$
7.2
Error reduction
$\max_s|\E_\pi[G_{t:t+n}|S_t=s]-v_\pi(s)|\le\gamma^n\max_s|V_{t+n-1}(s)-v_\pi(s)|$
7.3
n-step Sarsa return
$G_{t:t+n}=R_{t+1}+\dots+\gamma^{n-1}R_{t+n}+\gamma^nQ_{t+n-1}(S_{t+n},A_{t+n})$
7.4, 7.5
n-step Expected Sarsa
$G_{t:t+n}=R_{t+1}+\dots+\gamma^{n-1}R_{t+n}+\gamma^n\bar V_{t+n-1}(S_{t+n})$, $\ \bar V(s)=\sum_a\pi(a|s)Q(s,a)$
7.7, 7.8
Off-policy n-step TD
$V(S_t)\leftarrow V(S_t)+\alpha\rho_{t:t+n-1}[G_{t:t+n}-V(S_t)]$
7.9
IS ratio span
$\rho_{t:h}=\prod_{k=t}^{\min(h,T-1)}\pi(A_k|S_k)/b(A_k|S_k)$
7.10
Off-policy n-step Sarsa
$Q(S_t,A_t)\leftarrow Q+\alpha\rho_{t+1:t+n}[G_{t:t+n}-Q(S_t,A_t)]$
7.11
Control variate (v)
$G_{t:h}=\rho_t(R_{t+1}+\gamma G_{t+1:h})+(1-\rho_t)V_{h-1}(S_t)$
7.13
Control variate (q)
$G_{t:h}=R_{t+1}+\gamma\rho_{t+1}(G_{t+1:h}-Q_{h-1}(S_{t+1},A_{t+1}))+\gamma\bar V_{h-1}(S_{t+1})$
7.14
Tree backup
$G_{t:t+n}=R_{t+1}+\gamma\sum_{a\ne A_{t+1}}\pi(a|S_{t+1})Q(S_{t+1},a)+\gamma\pi(A_{t+1}|S_{t+1})G_{t+1:t+n}$
7.16
Q(σ)
$G_{t:h}=R_{t+1}+\gamma(\sigma_{t+1}\rho_{t+1}+(1-\sigma_{t+1})\pi(A_{t+1}|S_{t+1}))(G_{t+1:h}-Q_{h-1}(S_{t+1},A_{t+1}))+\gamma\bar V_{h-1}(S_{t+1})$
7.17
Chapter 9 — On-policy prediction with approximation
Value error
$\overline{\mathrm{VE}}(\mathbf w)=\sum_s\mu(s)[v_\pi(s)-\hat v(s,\mathbf w)]^2$
9.1
On-policy distribution
$\eta(s)=h(s)+\sum_{\bar s}\eta(\bar s)\sum_a\pi(a|\bar s)p(s|\bar s,a)$, $\ \mu(s)=\eta(s)/\sum_{s'}\eta(s')$
9.2, 9.3
SGD
$\mathbf w_{t+1}=\mathbf w_t+\alpha[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)$
9.5
General SGD target
$\mathbf w_{t+1}=\mathbf w_t+\alpha[U_t-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)$
9.7
Linear
$\hat v(s,\mathbf w)=\mathbf w^\top\mathbf x(s)$, $\ \nabla\hat v=\mathbf x(s)$
9.8
Linear TD(0)
$\mathbf w_{t+1}=\mathbf w_t+\alpha(R_{t+1}+\gamma\mathbf w_t^\top\mathbf x_{t+1}-\mathbf w_t^\top\mathbf x_t)\mathbf x_t$
9.9
A and b
$\mathbf A=\E[\mathbf x_t(\mathbf x_t-\gamma\mathbf x_{t+1})^\top]$, $\ \mathbf b=\E[R_{t+1}\mathbf x_t]$
9.11
TD fixed point
$\mathbf w_{TD}=\mathbf A^{-1}\mathbf b$
9.12
Error bound
$\overline{\mathrm{VE}}(\mathbf w_{TD})\le\frac1{1-\gamma}\min_\mathbf w\overline{\mathrm{VE}}(\mathbf w)$
9.14
n-step semi-gradient
$\mathbf w_{t+n}=\mathbf w_{t+n-1}+\alpha[G_{t:t+n}-\hat v(S_t,\mathbf w_{t+n-1})]\nabla\hat v(S_t,\mathbf w_{t+n-1})$
9.15
Polynomial basis
$x_i(s)=\prod_{j=1}^ks_j^{c_{i,j}}$, $\ (n+1)^k$ features
9.17
Fourier basis
$x_i(s)=\cos(\pi\,\mathbf s^\top\mathbf c^i)$; $\ \alpha_i=\alpha/\|\mathbf c^i\|$
9.18
RBF
$x_i(s)=\exp(-\|s-c_i\|^2/2\sigma_i^2)$
§9.5.5
Step-size rule
$\alpha=(\tau\E[\mathbf x^\top\mathbf x])^{-1}$; tile coding: $\alpha=1/(\tau n)$
9.19
LSTD
$\hat{\mathbf A}_t=\sum_k\mathbf x_k(\mathbf x_k-\gamma\mathbf x_{k+1})^\top+\varepsilon\mathbf I$, $\ \hat{\mathbf b}_t=\sum_kR_{k+1}\mathbf x_k$, $\ \mathbf w_t=\hat{\mathbf A}_t^{-1}\hat{\mathbf b}_t$
9.20, 9.21
Kernel regression
$\hat v(s,\mathcal D)=\sum_{s'\in\mathcal D}k(s,s')g(s')$; linear ⇔ $k(s,s')=\mathbf x(s)^\top\mathbf x(s')$
9.23, 9.24
Emphatic update
$\mathbf w_{t+n}=\mathbf w_{t+n-1}+\alpha M_t[G_{t:t+n}-\hat v(S_t)]\nabla\hat v(S_t)$, $\ M_t=I_t+\gamma^nM_{t-n}$
9.25, 9.26