Each chapter page ends with a cheat sheet of its key equations. This page collects them all, in book order. A ★ marks equations well known by name. Each “eq.” link opens the full explanation on the chapter page: the equation in words, term by term, and why it holds.
Introduction
Discounted return
\(\sum_{t=1}^{\infty} \gamma^{t-1} r_t\) eq.
★ Maximum expected utility
\(a^* = \arg\max_a \sum_{s'} P(s' \mid a, o)\, U(s')\) eq.
Constant reward \(r\) forever
\(r / (1 - \gamma)\) Problem 2
Part I — Probabilistic Reasoning
Normalization
\(\sum_x P(x) = 1\) , \(\ \int p(x)\,dx = 1\) eq.
★ Gaussian
\(\mathcal{N}(x \mid \mu, \sigma^2) = \frac{1}{\sigma\sqrt{2\pi}} e^{-(x-\mu)^2 / 2\sigma^2}\) eq.
Mixture
\(p(x) = \sum_i \rho_i \mathcal{N}(x \mid \mu_i, \sigma_i^2)\) eq.
★ Multivariate Gaussian
\(\mathcal{N}(\mathbf{x} \mid \boldsymbol\mu, \boldsymbol\Sigma)\) , with elliptical contourseq.
★ Conditional probability
\(P(x \mid y) = P(x, y) / P(y)\) eq.
Linear Gaussian
\(p(x \mid y) = \mathcal{N}(x \mid my + b, \sigma^2)\) eq.
Sigmoid
\(P(x^1 \mid y) = 1 / (1 + e^{-2(y - \theta_1)/\theta_2})\) eq.
★ Chain rule (Bayes net)
\(P(x_{1:n}) = \prod_i P(x_i \mid \mathrm{pa}(x_i))\) eq.
Conditional independence
\(P(x, y \mid z) = P(x \mid z) P(y \mid z)\) eq.
Enumeration
\(P(q \mid e) \propto \sum_h P(q, h, e)\) eq. exponential in hidden variables
★ Naive Bayes
\(P(c \mid o_{1:n}) \propto P(c) \prod_i P(o_i \mid c)\) eq. \(O(n \lvert C \rvert)\)
★ Sum-product
Push each \(\sum\) inside the factors that don’t mention it
eq. set by the largest factor
Rejection estimate
\(\#(q, e) / \#(e)\) eq. wastes a fraction \(1 - P(e)\)
Likelihood weight
\(w = \prod_{e_i} P(e_i \mid \mathrm{pa}(e_i))\) eq. every sample used
Gibbs update
\(P(x_i \mid x_{-i}) \propto P(x_i \mid \mathrm{pa}) \prod_{\text{children}} P(c \mid \mathrm{pa}(c))\) eq. per sweep: \(O(n)\) blanket updates
★ Gaussian conditioning
\(\boldsymbol\mu_{a \mid b} = \boldsymbol\mu_a + \boldsymbol\Sigma_{ab} \boldsymbol\Sigma_{bb}^{-1}(\mathbf{b} - \boldsymbol\mu_b)\) eq. \(O(d^3)\)
Log-likelihood
\(\ell(\theta) = \sum_i \log P(x_i \mid \theta)\) eq.
★ ML estimate (counts)
\(\hat\theta_{ijk} = m_{ijk} / \sum_{k'} m_{ijk'}\) eq.
Gaussian ML
\(\hat\mu = \frac1m \sum x_i\) , \(\ \hat\sigma^2 = \frac1m \sum (x_i - \hat\mu)^2\) eq.
★ Beta update
\(\mathrm{Beta}(\alpha, \beta) \to \mathrm{Beta}(\alpha + m_1, \beta + m_0)\) ; mean \(\frac{\alpha + m_1}{\alpha + \beta + m}\) eq.
Dirichlet posterior mean
\(\frac{\alpha_k + m_k}{\sum_{k'} (\alpha_{k'} + m_{k'})}\) eq.
Kernel density
\(\hat p(x) = \frac1m \sum_i \mathcal{N}(x \mid x_i, h^2)\) eq.
★ EM
E: expected counts from \(P(\text{missing} \mid \text{observed}, \theta)\) ; M: normalize them
eq.
★ Bayesian score
\(\ln P(G) + \sum_{i,j} \Big[\ln \frac{\Gamma(\alpha_{ij0})}{\Gamma(\alpha_{ij0} + m_{ij0})} + \sum_k \ln \frac{\Gamma(\alpha_{ijk} + m_{ijk})}{\Gamma(\alpha_{ijk})}\Big]\) eq.
Decomposability
\(\ln P(D \mid G) = \sum_i \mathrm{score}(x_i, \mathrm{pa}(x_i))\) eq.
Counting DAGs
\(a(n) = \sum_k (-1)^{k+1} \binom{n}{k} 2^{k(n-k)} a(n-k)\) eq.
★ Markov equivalence
same skeleton and same v-structures
eq.
BDeu prior
\(\alpha_{ijk} = \kappa / (q_i r_i)\) : score-equivalenteq.
★ Rational preference axioms
completeness, transitivity, continuity, independence
eq.
★ Expected utility of a lottery
\(U([S_1{:}\,p_1; \ldots]) = \sum_i p_i U(S_i)\) eq.
Certainty equivalent
\(U(x_{\text{ce}}) = \mathbb{E}[U(x)]\) eq.
Exponential utility
\(U(x) = 1 - e^{-\lambda x}\) , \(\ x_{\text{ce}} = -\frac1\lambda \ln \mathbb{E}[e^{-\lambda x}]\) eq.
Elicitation
\(S \sim [S_\top{:}\,p; S_\bot{:}\,1-p] \Rightarrow U(S) = p\) eq.
★ Maximum expected utility
\(a^* = \arg\max_a \sum_{s'} P(s' \mid a, o) U(s')\) eq.
★ Value of information
\(\sum_{o'} P(o' \mid o) EU^*(o, o') - EU^*(o)\) eq.
Part II — Sequential Problems
Value of a policy
\(U^\pi(s) = \mathbb{E}\big[\sum_t \gamma^t r_t \mid s_0 = s\big]\) eq. —
★ Bellman expectation equation
\(U^\pi(s) = R(s,\pi(s)) + \gamma \sum_{s'} T(s' \mid s,\pi(s))\, U^\pi(s')\) eq. \(O(\lvert\mathcal{S}\rvert^2)\) per sweep
Matrix form (exact evaluation)
\(\mathbf{U}^\pi = (\mathbf{I} - \gamma \mathbf{T}^\pi)^{-1} \mathbf{R}^\pi\) eq. \(O(\lvert\mathcal{S}\rvert^3)\)
★ Q-function (lookahead)
\(Q(s,a) = R(s,a) + \gamma \sum_{s'} T(s' \mid s,a)\, U(s')\) eq. \(O(\lvert\mathcal{S}\rvert^2 \lvert\mathcal{A}\rvert)\)
Greedy policy
\(\pi(s) = \arg\max_a Q(s,a)\) eq. \(O(\lvert\mathcal{S}\rvert \lvert\mathcal{A}\rvert)\) given \(Q\)
★ Bellman optimality equation
\(U^*(s) = \max_a Q^*(s,a)\) eq. —
★ Bellman backup
\(U_{k+1}(s) = \max_a \big(R(s,a) + \gamma \sum_{s'} T(s' \mid s,a)\, U_k(s')\big)\) eq. \(O(\lvert\mathcal{S}\rvert^2 \lvert\mathcal{A}\rvert)\)
Residual stopping rule
\(\lVert U_{k+1} - U_k \rVert_\infty < \epsilon(1-\gamma)/\gamma\) eq. \(O(\lvert\mathcal{S}\rvert)\)
Greedy policy from \(U_\theta\)
\(\pi(s) = \arg\max_a R(s,a) + \gamma \sum_{s'} T(s' \mid s,a) U_\theta(s')\) eq.
Approximate value iteration
back up \(u_i\) at each \(s_i\) , then \(\theta \leftarrow \operatorname{fit}(S, u)\)
eq.
Linear approximation
\(U_\theta(s) = \theta^\top \beta(s)\) eq.
\(k\) -nearest neighboraverage of the \(k\) closest stored values
eq.
Kernel smoothing
\(\beta_i(s) = k(s, s_i) / \sum_j k(s, s_j)\) eq.
Bilinear interpolation
corner weights = opposite areas
eq.
Simplex interpolation
\(d+1\) corners, weights = gaps between sorted fractionseq.
★ Least squares
\(\theta = (X^\top X)^{-1} X^\top u = X^+ u\) eq.
Neural network regression
\(\theta \leftarrow \theta - \alpha \nabla_\theta \text{MSE}\) eq.
Forward search
\(U_d(s) = \max_a R(s,a) + \gamma \sum_{s'} T(s' \mid s,a) U_{d-1}(s')\) , \(U_0 = U\) eq.
Rollout estimate
\(\hat U^\pi(s) = \sum_{t=1}^d \gamma^{t-1} r_t\) eq.
Branch and bound
skip \(a\) if \(\overline{Q}(s,a) <\) best found
eq.
Sparse sampling
\(\hat Q_d(s,a) = \frac1m \sum_i \big(r^{(i)} + \gamma \max_{a'} \hat Q_{d-1}(s'^{(i)}, a')\big)\) eq.
★ UCB1
\(Q(s,a) + c\sqrt{\log N(s) / N(s,a)}\) eq.
MCTS update
\(Q \leftarrow Q + (q - Q)/N\) eq.
Heuristic search
greedy walks; \(U(s) \leftarrow \max_a (R + \gamma \sum T U)\) from \(\overline U \ge U^*\)
eq.
Solved state
residual \(< \delta\) on the greedy envelope
eq.
Open-loop planning
\(\max_{a_{1:d}} \mathbb{E}\big[\sum_t \gamma^{t-1} R\big]\) eq.
Deterministic MPC
\(\max \sum_t \gamma^t R(s_t,a_t)\) s.t. \(s_{t+1} = T(s_t,a_t)\) eq.
Policy value
\(U(\theta) = \mathbb{E}_\tau[R(\tau)]\) eq.
Monte Carlo evaluation
\(\hat U = \frac1m \sum_i R(\tau^{(i)})\) , variance \(\operatorname{Var}[R]/m\) eq.
Hooke–Jeeves
best of \(\theta, \theta \pm \alpha e_i\) ; else \(\alpha \leftarrow c\alpha\)
eq.
Genetic algorithm
child = random elite \(+\ \sigma\epsilon\)
eq.
Search objective
\(\max_\psi \mathbb{E}_{\theta \sim p(\cdot\mid\psi)}[U(\theta)]\) eq.
Cross entropy
refit \(\mu, \Sigma\) to the elites
eq.
★ Search gradient
\(\mathbb{E}[U(\theta)\nabla_\psi \log p(\theta \mid \psi)]\) eq.
Rank weights
\(w^{(i)} \propto \max(0, \log(\frac m2 + 1) - \log i)\) , minus \(\frac1m\) eq.
Isotropic ES
\(\frac1\sigma \sum_i w^{(i)} \epsilon^{(i)}\) , with \(\pm\epsilon\) pairseq.
Finite difference
\(\big(U(\theta + \delta e_i) - U(\theta)\big)/\delta\) eq.
Regression gradient
\(\Delta\Theta^+ \Delta U\) eq.
★ Likelihood ratio
\(\mathbb{E}_\tau[\nabla\log p_\theta(\tau) R(\tau)]\) , \(\nabla\log p_\theta(\tau) = \sum_k \nabla\log\pi_\theta(a^{(k)} \mid s^{(k)})\) eq.
Reward-to-go
\(\mathbb{E}\big[\sum_k \nabla\log\pi_\theta\, \gamma^{k-1} r_{\text{to-go}}^{(k)}\big]\) eq.
★ Baseline (REINFORCE)
\(\mathbb{E}\big[\sum_k \nabla\log\pi_\theta\, \gamma^{k-1} (r_{\text{to-go}}^{(k)} - r_{\text{base}}(s^{(k)}))\big]\) eq.
Best constant baseline
\(\mathbb{E}[\ell_i^2 r_{\text{to-go}}] / \mathbb{E}[\ell_i^2]\) eq.
Advantage form
\(\mathbb{E}\big[\sum_k \nabla\log\pi_\theta\, \gamma^{k-1} A_\theta(s^{(k)}, a^{(k)})\big]\) eq.
Gradient ascent
\(\theta \leftarrow \theta + \alpha \nabla U\) eq.
Restricted step
\(\theta + \sqrt{2\epsilon}\, \nabla U / \lVert\nabla U\rVert\) eq.
Fisher information
\(F = \mathbb{E}[\nabla\log p\, \nabla\log p^\top]\) ; \(D_{\text{KL}} \approx \frac12 \Delta^\top F \Delta\) eq.
★ Natural gradient
\(\theta + \sqrt{2\epsilon / \nabla U^\top u}\ u\) , \(u = F^{-1}\nabla U\) eq.
Surrogate objective
\(\mathbb{E}\big[\frac{\pi_{\theta'}}{\pi_\theta} A_\theta\big]\) eq.
Trust region (TRPO)
accept if surrogate improves and \(\mathbb{E}_s[D_{\text{KL}}] \le \epsilon\) ; else halve
eq.
★ PPO clipped objective
\(\mathbb{E}[\min(wA, \operatorname{clamp}(w, 1\pm\epsilon)A)]\) eq.
★ TD residual
\(\delta_k = r_k + \gamma U_\phi(s_{k+1}) - U_\phi(s_k)\) eq.
Critic gradient
\(\sum_k (U_\phi(s_k) - r_{\text{to-go}}^{(k)}) \nabla_\phi U_\phi(s_k)\) eq.
\(k\) -step advantage\(\sum_{\ell \le k} \gamma^{\ell-1} r_\ell + \gamma^k U(s_{k+1}) - U(s) = \sum_{\ell \le k}\gamma^{\ell-1}\delta_\ell\) eq.
★ GAE
\(\sum_k (\gamma\lambda)^{k-1} \delta_k\) eq.
★ Deterministic policy gradient
\(\mathbb{E}_s[\nabla_\theta\pi_\theta(s)\, \nabla_a Q_\phi(s, a)]\) eq.
PUCT
\(Q(s,a) + c\,\pi_\theta(a \mid s)\sqrt{N(s)}/(1 + N(s,a))\) eq.
Tree search targets
\(\pi_{\text{MCTS}} \propto N^\eta\) , \(U_{\text{MCTS}} = \max_a Q\) eq.
Performance metric
\(f(\pi) = \mathbb{E}_\tau[f_{\text{traj}}(\tau)]\) , \(P(\tau) = b(s_1)\prod_t T(s_{t+1} \mid s_t, \pi(s_t))\) eq.
Additive metric
\(f(\pi) = \sum_s f_{\text{state}}(s)\, b(s)\) by policy evaluationeq.
★ Standard error
\(\hat\sigma/\sqrt n\) ; relative: \(\hat\sigma/(\hat\mu\sqrt n)\) eq.
★ Importance sampling
\(\frac1n\sum_i f_{\text{traj}}(\tau^{(i)})\,P(\tau^{(i)})/P'(\tau^{(i)})\) , \(\tau^{(i)} \sim P'\) eq.
Optimal proposal
\(P^* \propto |f_{\text{traj}}|\,P\) ; per step \(P'(\nu \mid s) \propto P(\nu)\,\hat U(s')\) eq.
Robust Bellman update
\(\max_a \min_i (R_i + \gamma \sum_{s'} T_i U_k)\) eq.
Pareto dominance
no worse on every metric, better on one
eq.
Adversarial reward
\(-R(s, \pi(s)) + \lambda \log T(s' \mid s, \pi(s))\) eq.
Part III — Model Uncertainty
★ Regret
\(h\theta^* - \mathbb{E}[\sum_t r_t] = \mathbb{E}[\sum_t (\theta^* - \theta_{a_t})]\) eq.
★ Posterior win probability
\(\rho_a = (w_a + 1)/(w_a + \ell_a + 2)\) eq.
ε-greedy
random arm w.p. \(\varepsilon_t\) , else greedy; \(\varepsilon_{t+1} = \alpha\varepsilon_t\)
eq.
Softmax
\(P(a) \propto \exp(\lambda\rho_a)\) eq.
Quantile
\(\arg\max_a F^{-1}_{\text{Beta}(w_a+1, \ell_a+1)}(\alpha)\) eq.
★ UCB1
\(\arg\max_a \rho_a + c\sqrt{\log N / N(a)}\) eq.
★ Thompson sampling
\(\tilde\theta_a \sim \text{Beta}(w_a + 1, \ell_a + 1)\) ; pull \(\arg\max_a \tilde\theta_a\) eq.
Bayes-optimal values
\(Q^*_r = \rho_a(1 + U^*_{r-1}(\text{win})) + (1 - \rho_a)U^*_{r-1}(\text{loss})\) eq.
Maximum likelihood model
\(\hat T = N(s, a, s')/N(s, a)\) , \(\hat R = \rho(s, a)/N(s, a)\) eq.
Prioritized sweeping priority
\(\max_{a^-} \hat T(s \mid s^-, a^-)\,|U(s) - u|\) eq.
R-MAX model
under-tried: reward \(r_{\max}\) , self-loop; else maximum likelihood
eq.
★ Dirichlet posterior
\(\mathrm{Dir}(\boldsymbol\alpha_0 + \mathbf N(s, a))\) ; predictive \(\alpha(s, a, s')/\sum_{s''}\alpha(s, a, s'')\) eq.
Bayes-adaptive Bellman equation
\(U^*(s, b) = \max_a (R + \gamma \sum_{s'} P(s' \mid s, b, a) U^*(s', \tau(s, b, a, s')))\) eq.
Incremental mean
\(\hat x \leftarrow \hat x + \alpha(x - \hat x)\) ; \(\sum\alpha = \infty\) , \(\sum\alpha^2 < \infty\) eq.
★ Q-learning
\(Q(s, a) \mathrel{+}= \alpha(r + \gamma\max_{a'}Q(s', a') - Q(s, a))\) eq.
★ Sarsa
\(Q(s, a) \mathrel{+}= \alpha(r + \gamma Q(s', a') - Q(s, a))\) eq.
Sarsa(λ)
\(Q \mathrel{+}= \alpha\delta N\) , \(N \leftarrow \gamma\lambda N\) eq.
★ Potential-based shaping
\(F(s, a, s') = \gamma\beta(s') - \beta(s)\) eq.
Gradient Q-learning
\(\theta \mathrel{+}= \alpha(r + \gamma\max_{a'}Q_\theta(s', a') - Q_\theta(s, a))\nabla_\theta Q_\theta(s, a)\) eq.
Experience replay
average the gradient over a random batch from a buffer
eq.
Behavioral cloning
\(\max_\theta \sum_{(s, a) \in \mathcal{D}} \log\pi_\theta(a \mid s)\) eq.
DAgger
add \((s, \pi_E(s))\) for states the learner visits; retrain on all data
eq.
SMILe mixture
\((1 - \beta)^k\pi_E + \sum_{i \le k}\beta(1 - \beta)^{i-1}\hat\pi^{(i)}\) eq.
★ Feature expectations
\(\mathbb{E}[U] = \phi^\top\mu_\pi\) , \(\mu_\pi = \mathbb{E}[\sum_k \gamma^{k-1}\beta(s^{(k)}, a^{(k)})]\) eq.
Maximum margin weights
\(\max t\) s.t. \(\phi^\top\mu_E \ge \phi^\top\mu^{(i)} + t\) , \(\|\phi\| \le 1\) eq.
★ Maximum entropy IRL
\(P_\phi(\tau) \propto \exp R_\phi(\tau)\) ; gradient = demo counts − expected countseq.
GAIL
\(\min_\theta\max_\phi \mathbb{E}_{\pi_\theta}[\log C_\phi] + \mathbb{E}_{\mathcal{D}}[\log(1 - C_\phi)]\) eq.
Part IV — State Uncertainty
Belief
\(b(s) = P(s_t = s \mid a_{1:t}, o_{1:t})\) eq. —
★ Bayes’ rule
\(P(s \mid o) \propto P(o \mid s)\, P(s)\) eq. —
★ Belief update (Bayes filter)
\(b'(s') \propto O(o \mid a, s') \sum_s T(s' \mid s, a)\, b(s)\) eq. \(O(\lvert\mathcal{S}\rvert^2)\)
★ Kalman predict
\(\boldsymbol\mu_p = \mathbf{T}_s \boldsymbol\mu_b + \mathbf{T}_a a,\ \ \boldsymbol\Sigma_p = \mathbf{T}_s \boldsymbol\Sigma_b \mathbf{T}_s^\top + \boldsymbol\Sigma_s\) eq. \(O(d^3)\)
★ Kalman gain and correct
\(\mathbf{K} = \boldsymbol\Sigma_p \mathbf{O}_s^\top (\mathbf{O}_s \boldsymbol\Sigma_p \mathbf{O}_s^\top + \boldsymbol\Sigma_o)^{-1}\) , \(\ \boldsymbol\mu_b' = \boldsymbol\mu_p + \mathbf{K}(o - \mathbf{O}_s \boldsymbol\mu_p)\) eq. \(O(d^3)\)
Particle weights
\(w^{(i)} \propto O(o \mid a, s'^{(i)})\) , \(s'^{(i)} \sim T(\cdot \mid s^{(i)}, a)\) eq. \(O(N)\)
★ Belief-state MDP
\(R(b, a) = \sum_s R(s, a)b(s)\) ; \(b' = \text{Update}(b, a, o)\) w.p. \(P(o \mid b, a)\) eq.
Conditional plan utility
\(U^\pi(s) = R(s, \pi()) + \gamma\sum_{s'}T\sum_o O\,U^{\pi(o)}(s')\) eq.
★ Alpha vectors
\(U^\pi(b) = \alpha_\pi^\top b\) ; \(U^*(b) = \max_\pi \alpha_\pi^\top b\) eq.
One-step lookahead
\(\arg\max_a R(b, a) + \gamma\sum_o P(o \mid b, a)U^\Gamma(\text{Update}(b, a, o))\) eq.
Dominance LP
\(\max\delta\) s.t. \(\alpha^\top b \ge \alpha'^\top b + \delta\) , \(b\) a distributioneq.
★ POMDP value iteration backup
\(\alpha(s) = R(s, a) + \gamma\sum_{s'}T(s' \mid s, a)\sum_o O(o \mid a, s')\alpha_o(s')\) eq.
Certainty equivalence
\(a = -K\mu_b\) eq.
★ QMDP
\(\alpha_a(s) = R(s, a) + \gamma\sum_{s'}T(s' \mid s, a)\max_{a'}\alpha_{a'}(s')\) eq.
Fast informed bound
\(\alpha_a(s) = R + \gamma\sum_o\max_{a'}\sum_{s'}O\,T\,\alpha_{a'}(s')\) eq.
BAWS and blind bounds
\(\max_a\min_s R(s, a)/(1 - \gamma)\) ; \(\alpha_a = R + \gamma T\alpha_a\) eq.
★ Point-based backup
best \(\alpha_{a,o}\) at \(\text{Update}(b, a, o)\) , combined, best at \(b\)
eq.
Sawtooth
\(\min_{(b', u')}\, u_E^\top b + \rho(b, b')(u' - u_E^\top b')\) eq.
Gap-driven search
follow \(\pi_{\text{hi}}\) , the widest-gap observation; stop at \(\delta/\gamma^d\)
eq.
Triangulation
\(U(b) = \sum_i\lambda_i U(b^{(i)})\) over the enclosing grid simplexeq.
Forward search
\(Q_d(b, a) = R(b, a) + \gamma\sum_o P(o \mid b, a)\,U_{d-1}(b'_o)\) eq. \(O((|\mathcal{A}||\mathcal{O}|)^d)\)
Depth error
\(|U_d - U^*| \le \gamma^d \varepsilon\) eq.
Branch and bound
skip \(a\) if \(Q_{\text{hi}}(b, a) \le\) best found
eq. at most forward search
Sparse sampling
average of \(m\) samples of \(r + \gamma U_{d-1}(b')\)
eq. \(O((|\mathcal{A}|\,m)^d)\)
★ UCB1 over histories
\(Q(h, a) + c\sqrt{\log N(h)/N(h, a)}\) eq. \(O(m\,d)\) for \(m\) simulations
Determinized successor
first \((s', o)\) with cumulative \(P \ge \Phi_{ij}\)
eq. \(O(|\mathcal{A}|^d m)\)
Gap-guided search
\(\arg\max_a Q_{\text{hi}}\) , then the widest-gap observationeq. per exploration \(O(d\,|\mathcal{A}||\mathcal{O}|)\)
Controller evaluation
\(U(x, s) = \sum_a \psi(a \mid x)[R(s, a) + \gamma\sum_{s'} T \sum_o O \sum_{x'} \eta\, U(x', s')]\) eq.
Node values over beliefs
\(U(x, b) = \alpha_x^\top b\) ; start at \(\arg\max_x \alpha_x^\top b\) eq.
Pointwise dominance
\(U(x, s) \le U(x', s)\) for all \(s\) eq.
Fixed-size program
\(\max \sum_s b(s) U(x_1, s)\) s.t. eq. , \(\psi\) and \(\eta\) distributionseq.
Controller gradient
\(v^\top(\partial r_\theta + \gamma\,\partial T_\theta\, u_\theta)\) , \(v = (I - \gamma T_\theta)^{-\top}\beta\) eq.
Simplex projection
\(\max(y - \tau, 0)\) , \(\tau\) so it sums to 1eq.
Part V — Multiagent Systems
Utility
\(U^i(\boldsymbol{\pi}) = \sum_{\boldsymbol{a}} R^i(\boldsymbol{a}) \prod_j \pi^j(a^j)\) eq.
Best response
\(\arg\max_{a^i} U^i(a^i, \boldsymbol{\pi}^{-i})\) eq.
Softmax response
\(\pi^i(a^i) \propto \exp(\lambda U^i(a^i, \boldsymbol{\pi}^{-i}))\) eq.
★ Nash equilibrium
\(U^i(\boldsymbol{\pi}) \ge U^i(a^i, \boldsymbol{\pi}^{-i})\) for all \(i, a^i\) eq.
★ Correlated equilibrium
\(\sum_{\boldsymbol{a}^{-i}} [R^i(a^i, \boldsymbol{a}^{-i}) - R^i(a^{i\prime}, \boldsymbol{a}^{-i})]\,\pi(a^i, \boldsymbol{a}^{-i}) \ge 0\) eq.
Fictitious play
best-respond to \(\hat{\pi}^j \propto N(j, \cdot)\)
eq.
Policy evaluation
\(U^{\boldsymbol{\pi}, i}(s) = R^i(s, \boldsymbol{\pi}(s)) + \gamma \sum_{s'} T(s' \mid s, \boldsymbol{\pi}(s)) U^{\boldsymbol{\pi}, i}(s')\) eq.
Best response MDP
\(T' = T(s' \mid s, a^i, \boldsymbol{\pi}^{-i}(s))\) , \(R' = R^i(s, a^i, \boldsymbol{\pi}^{-i}(s))\) eq.
★ Nash equilibrium
no agent gains by deviating, in any state
eq.
Fictitious play
best-respond to \(\hat{\pi}^j(a^j \mid s) \propto N(j, a^j, s)\)
eq.
Nash Q-learning
\(Q^i \leftarrow Q^i + \alpha(R^i + \gamma\, U^i_{\text{stage}}(s') - Q^i)\) eq.
Joint plan evaluation
\(U^{\boldsymbol{\pi}}(s) = R(s, \boldsymbol{\pi}()) + \gamma \sum_{s'} T \sum_{\boldsymbol{o}} O\, U^{\boldsymbol{\pi}(\boldsymbol{o})}(s')\) eq.
Joint controller evaluation
\(U(\boldsymbol{x}, s) = \sum_{\boldsymbol{a}} \prod_i \psi^i [R + \gamma \sum T \sum O \sum_{\boldsymbol{x}'} \prod_i \eta^i\, U(\boldsymbol{x}', s')]\) eq.
Game over plans
actions \(\Pi^i_h\) , rewards \(U^{\boldsymbol{\pi}, i}(b)\)
§26.3
Pruning LP
\(\max \delta\) : some \(b(\boldsymbol{\pi}^{-i}, s)\) makes \(\pi^i\) beat every alternative by \(\delta\) eq.
Dec-POMDP objective
\(\max_{\boldsymbol{\pi}} U^{\boldsymbol{\pi}}(b)\) , plans branching on own observationseq.
Communication bound
\(\max_{\boldsymbol{\pi}} U^{\boldsymbol{\pi}}(b) \le U^*_{\text{MPOMDP}}(b)\) eq.
JESP step
\(\pi^i \leftarrow \arg\max_{\pi^{i\prime}} U^{\pi^{i\prime}, \boldsymbol{\pi}^{-i}}(b)\) eq.
MBDP
keep \(m\) plans per agent, chosen at sampled beliefs
§27.5
Controllers
maximize \(\sum_s b(s) U(\boldsymbol{x}_1, s)\) over all \(\psi^i, \eta^i\) (eq. 26.3 constraints)
§27.6